1．数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。
2. 对于给定的 n 个元素,可以构造出的逻辑结构有 线性结构 、树形结构、图形结构、集合四种。
3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4．一个数据结构在计算机中表示（又称映像）称为存储结构。
5．抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是 时间复杂度 和 空间复杂度 。
7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。
8． 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出。
11.下面程序段中带下划线的语句的执行次数的数量级是（log2n）
i=1； WHILE i i=1； while (i x=x+1； i=i*2； 15. 下面程序段的时间复杂度为 O(n) 。(n>1) sum=1； for (i=0；sum 逻辑结构、存储结构、操作（运算） 4．在一个长度为 n 的顺序表中第 i个元素（1<=i<=n）之前插入一个元素时，需向后移动 n-i+1 个元素。 5．在单链表中设置头结点的作用是 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。 10．链接存储的特点是利用 指针 来表示数据元素之间的逻辑关系。 11.顺序存储结构是通过 物理上相邻 表示元素之间的关系的;链式存储结构是通过 指针 表示元素之间的关系的。 12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共4 个，单链表为 2 个。 15. 带头结点的双循环链表 L 中只有一个元素结点的条件是： L->next->next==L 16. 在单链表 L 中，指针 p 所指结点有后继结点的条件是： p->next!=null 17.带头结点的双循环链表 L 为空表的条件是： L->next==L && L->prior==L 。 18. 在单链表 p 结点之后插入 s 结点的操作是： s->next=p->next;p->next=s; 。 1．栈是 操作受限 的线性表，其运算遵循 后进先出 的原则。 2． 栈 是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3 则不可能的栈输出序列是 312 。 4. 设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 23 ，而栈顶指针值是 100C H。设栈为顺序栈，每个元素占 4 个字节。 5. 当两个栈共享一存储区时，栈利用一维数组 stack(1,n)表示，两栈顶指针为 top[1]与 top[2]，则当栈1 空时，top[1]为 0 ，栈2 空时 ，top[2]为 n+1 ，栈满时为 top[1]+1=top[2] 。 6．两个栈共享空间时栈满的条件 两栈顶指针值相减的绝对值为1（或两栈顶指针相邻） 。 8. 多个栈共存时，最好用 链式存储结构 作为存储结构。 9．用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S和X 的操作串为 S×SS×S×× 。 10. 顺序栈用 data[1..n]存储数据，栈顶指针是 top,则值为 x 的元素入栈的操作是 data[++top]=x；。 11．表达式23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是 23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数） 12. 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。 14． 队列 又称作先进先出表。 15. 队列的特点是先进先出 。 16．队列是插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 先进先出 。 17. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是 s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s； 。 18．区分循环队列的满与空，只有两种方法，它们是 牺牲一个存储单元 和 设标记 。 21．表达式求值是 栈 应用的一个典型例子。 22．循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别是 front 和 rear ，则当前队列的元素个数是（rear-front+m）% m 。 23．设 Q[0..N-1]为循环队列，其头、尾指针分别为 P 和 R，则队 Q 中当前所含元素个数为（R-P+N）% N。 1．空格串是指 由空格字符（ASCII值32）所组成的字符串 ，其长度等于 空格个数 。 2．组成串的数据元素只能是 字符 。 3．一个字符串中 任意个连续的字符组成的子序列 称为该串的子串 。 4．INDEX（‘DATASTRUCTURE’，‘STR’）= 5 。 8．设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为 模式匹配 ，又称P 为 模式串 。 9．串是一种特殊的线性表，其特殊性表现在 其数据元素都是字符 ；串的两种最基本的存储方式是 顺序存储 、 链式存储 ；两个串相等的充分必要条件是 串的长度相等且两串中对应位置的字符也相等 。 10．两个字符串相等的充分必要条件是 两串的长度相等且两串中对应位置的字符也相等 。 11．知U=‘xyxyxyxxyxy’；t=‘xxy’； ASSIGN（S，U）； ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））； ASSIGN（m，‘ww’） 求REPLACE（S，V，m）=’xyxyxywwy’。 1. 数组的存储结构采用 顺序存储结构 存储方式。 3. 设数组 a[1..50,1..80]的基地址为2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为 9174 ;若以列序为主序顺序存储，则元素 a[45,68]的存储地址为 8788 。 4. 将整型数组 A[1..8，1..8]按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A[7，3]的地址是： 1100 。 6. 设有二维数组 A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为 100，若按列优先顺序存储，则元素 A[6,6]存储地址为 232 。 11．设n 行n 列的下三角矩阵 A 已压缩到一维数组 B[1..n*（n+1）/2]中，若按行为主序存储，则 A[i,j]对应的 B 中存储位置为 i(i-1)/2+j (1<=i,j<=n) 。 14. 设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储：a11=1），则 a85 的地址为 33 (k=i(i-1)/2+j) (1<=i,j<=n) 。 15. 所谓稀疏矩阵指的是 非零元很少(t< 17. 上三角矩阵压缩的下标对应关系为： 上三角矩阵中，主对角线上第r(1£r£n) 行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j (i£j)。 18. 假设一个 15 阶的上三角矩阵 A按行优先顺序压缩存储在一维数组 B 中， 则非零元素 A9,9在 B中的存储位置k= 93 。 （注：矩阵元素下标从 1 开始）如果按行序为主序将下三角元素 Ai j (i,j)存储在一个一维数组 B[ 1..n(n+1)/2]中，对任一个三角矩阵元素 A ,它在数组B 中的下标为 i(i-1)/2+j 。 8．深度为k 的完全二叉树至少有1个结点，至多有2个结点。 42．一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排 序的过程。 50．线索二元树的左线索指向其 ，右线索指向其 。 53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。 22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是 深度优先 遍历方法。 28. Prim（普里姆）算法适用于求 边稠密 的网的最小生成树； 29．克鲁斯卡尔算法的时间复杂度为 O(eloge）,它对 边稀疏 图较为适合。 34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按 递增 次序依次产生，该算法弧上的权出现 负值 情况时，不能正确产生最短路径。 12. 在哈希函数H（key）=key%p 中，p 值最好取 。 49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列; 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 比较 和记录的 移动 。 6．直接插入排序用监视哨的作用是 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 1. 文件可按其记录的类型不同而分成两类，即 操作系统文件 和 数据库 文件。 7. 索引顺序文件既可以顺序存取，也可以 随机 存取。 8. 建立索引文件的目的是 提高查找速度 。 9. 索引顺序文件是最常用的文件组织之一，通常用 树 结构来组织索引。 10. 倒排序文件的主要优点在于 检索记录快 。 13. VSAM 系统是由索引集、顺序集、数据集构成的。 31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于b 32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是 (x,y,z) 。 33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是 (d,e) 。 4、应用题 1．线性表有两种存储结构：一是顺序表，二是链表。试问： 如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O。 选顺序存储结构。顺序表可以随机存取，时间复杂度为O。 2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。 3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？ 采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。 44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） 46．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC 画出这棵二叉树。 画出这棵二叉树的后序线索树。 将这棵二叉树转换成对应的树（或森林） 43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。下载本文
