三、填空题
1．数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。
2. 对于给定的 n 个元素,可以构造出的逻辑结构有 线性结构 、树形结构、图形结构、集合四种。
3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4．一个数据结构在计算机中表示（又称映像）称为存储结构。
5．抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
6．数据结构中评价算法的两个重要指标是 时间复杂度 和 空间复杂度 。
7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。
8． 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出。
11.下面程序段中带下划线的语句的执行次数的数量级是（log2n）
i=1； WHILE i<n DO i=i*2;
12. 下面程序段中带下划线的语句的执行次数的数量级是(nlog2n )。
i=1；
while (i<n)
  for(i=1;i<=n;i++)
x=x+1；
i=i*2；
15. 下面程序段的时间复杂度为  O(n)  。(n>1) 
        sum=1；
        for (i=0；sum<n；i++) sum+=1； 
8．对于一个数据结构，一般包括哪三个方面的讨论
逻辑结构、存储结构、操作（运算）
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. 顺序栈用 ]存储数据，栈顶指针是 top,则值为 x 的元素入栈的操作是 data[++top]=x；。
11．表达式23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是 （注：表达式中的点(.)表示将数隔开，如是三个数）
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．循环队列用数组 -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 。
二叉树的深度为k8．设 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 已压缩到一维数组 *（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<<m*n)且分布没有规律 。
16. 对矩阵压缩是为了 节省存储空间 。
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．直接插入排序用监视哨的作用是 免去查过程中每一步都要检测整个表是否查完毕，提高了查效率。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。