一、 单选题 1.
数据结构研究( )。
A.数据的逻辑结构、存储结构及操作的实现 B. 数据的物理结构 C. 数据的逻辑结构与存储结构 D. 数据的逻辑结构。
数据的存储结构包括顺序;链式;散列和( )4 种基本类型。 A. Vector B. Index C. Sets D. Array 若某线性表最常用的操作是取第 i 个元素，则采用( )存储方式最节省运算时间。 A．双链表 B． 单链表 C．顺序表 D． 单循环链表
一个单链表中，已知*q 结点是*p 结点的前趋结点，若在*q 和*p 之间插入*s 结点， 则必须执行( )操作。
A．q->next=p ->next; p ->next=s; B． p ->next=s; s->next=q C．p ->next=s->next; s->next=p D．q->next=s; s->next= p ;
在一个具有n个结点的有序单链表中，若插入一个新结点，单链表仍然有序，则算法的 时间复杂度为（ ）。 A．O(n) B．O(1) C．O(n2) D．O(nlog2n) 队列与一般线性表的区别在于( )。
A. 数据元素的类型不同 B. 插入或删除操作的位置受限制 C. 数据元素的个数不同 D. 逻辑结构不同
设进栈的顺序为 a b c d，则不可能得到的出栈序列是( )。 A.a b c d B.d c b a C. d a b c D. a c d b 用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改
循环队列的队满条件为（在牺牲一个存储空间的情况下） ( )
A. rear % maxsize ==(front+1) % maxsize; B. (rear+1)% maxsize == front+1 C. (rear+1)% maxsize == front D. rear == front 下面关于串的叙述中，哪一个是不正确的( )
A.串是字符的有限序列 B. 模式匹配是串的一种重要运算
C. 空串是由空格构成的串 D.串既可以采用顺序存储，也可以采用链式存储 稀疏矩阵一般的压缩存储方法有( )两种。
A．三元组表和十字链表 B．三元组表和哈希表 C．二维数组和三维数组 D．哈希表和十字链表
中序遍历一颗二叉排序树所得到的结点访问序列是结点值的( )序列。 A.递增或递减 B.递增 C. 递减 D. 无序
在树中，若结点A 有四个兄弟，而且B 是A 的双亲，则B 的度为( )。 A.3 B.4 C.5 D.6
若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是( ) A．9 B．11 C．12 D、不确定 n 个顶点的连通图至少有( )条边 A. 0 B. n C. n+1 D. n-1
若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。 A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵
- 0 -
2. 3. 4.
5.
6.
7. 8.
9.
10.
11.
12. 13. 14. 15. 16.
17. AOV网是一种( )。
A．有向图 B．无向图 C．有向无环图 D．无向无环图 18. 采用折半查找方法进行查找，数据文件应为( )。
A．有序表和链式存储结构 B ．有序表和顺序存储结构 C． 随机表和顺序存储结构 D ．随机表和链式存储结构
19. 在顺序表{2、5、7、10、14、15、18}中，用二分法查找关键码 12需做( )次关键码
比较。 A．2 B．3 C．1 D．5
20. 下面的排序算法中，时间复杂度不是O(n2）的是( )。
A.直接插入排序 B.冒泡排序 C.二路归并排序 D.直接选择排序 21. 算法指的是（ ）
A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列
22. 下列数据结构中，（ ）是线性结构。
A．树 B ．队列 C．图 D ．A 和B 23. 下面程序的时间复杂为（ ）
for（i=1，s=0； i<=n； i++） { t=1；
for(j=1；j<=i；j++) t=t*j； s=s+t； } A. O(n) B. O(n2) C. O(n3) D.O(n4) 24. 用链表表示线性表的优点是 ( )。
A. 便于随机存取 B. 花费的存储空间比顺序表少
C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同
25. 从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需
平均比较( )个结点。
A．n B．n/2 C．（n-1 ）/2 D．(n+1)/2
26. 在一个单链表中，已知 q 所指节点是 p 所指节点的前驱节点，若在 q 和 p 之间插
入 s 节点，则执行( )。
A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 27. 栈的插入和删除操作在（ ）进行。
A 栈顶 B 栈底 C 任意位置 D 指定位置 28. 设栈的输入序列是 1 2 3 4,则( )是不可能的出栈序列。
A.1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 29. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，
则执行出队操作后其头指针front值为（ ）
A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 30. 如下陈述中正确的是（ ）
A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串
- 1 -
31. 树型结构中元素间存在( )的关系。
A. 一对一 B. 多对多 C. 一对多 D. 随机 32. 一棵深度为 5 的满二叉树中,结点的总数为 ( )。
A.31 B.32 C.33 D.16 33. 一棵二叉树有 67 个结点，这些结点的度或者是 0，或者是 2。这棵二叉树中度为 2 的
结点有( )个。
A. 33 B.34 C.32 D.30 34. 下面关于图的存储的叙述中正确的是（ ）
A.邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关； B.邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关； C.邻接表占用的存储空间只与图中结点个数有关，而与边数无关； D.邻接表占用的存储空间只与图中边数有关，而与结点个数无关。
35. n 个顶点的连通图至少有( )条边。
A．n-1 B．n C．n+1 D ．0 36. AOV网是一种（ ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
37. 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。
A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵 38. 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列
A. 前序 B. 中序 C.后序 D.按层序
39. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}, 如果采用二分查找法, 查
值为 82 的结点时，（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8
40. 假定有 K 个关键字互为同义词,若用线性探测法把这 K 个关键字存入散列表中,至少
要进行( )次探测。
A.K-1 次 B. K(K-1)/2 次 C.K+1 次 D.K(K+1)/2 次 41. 对一个算法的评价，不包括如下（ ）方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度
42. 对线性表，在下列哪种情况下应当采用链表表示？( )
A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变
43. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL;
44. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素 C.都是先进先出 A. 2 3 1 C. 3 1 2
B.都是先进后出 D.没有共同点
- 2 -
45. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )
B. 3 2 1 D. 1 2 3
46. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，
则执行出队操作后其头指针front值为（ ）
A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m
47. 用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改
48. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在
676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．696
49. 树最适合用来表示( )。
A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
50. 二叉树的第k层的结点数最多为( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k+1
51. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分
查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3 C. 9，5，3
B. 9，5，2，3 D. 9，4，2，3
52. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
A. O（1） B. O（n） C. O（1og2n） D. O（n2）
53. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）
=K %9作为散列函数，则散列地址为1的元素有（ ）个，
A．1 B．2 C．3 D．4
54. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
55. AOV网是一种（ ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
56. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
A. 堆排序
B. 冒泡排序 C. 希尔排序 D. 快速排序
57. 快速排序在最坏情况下的时间复杂度为（ ）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)
58. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
59. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序
时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
- 3 -
15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84
则所采用的排序方法是（ ）
A．选择排序 B．希尔排序 C．归并排序 D．快速排序
60. 设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
61.下面程序段的时间复杂度为（ ）。 for(i=0;i A. O(m-1)*O(n-1) B. O((m-1)*(n-1)) C. O((m+1)*(n+1)) D. O(m*n) 62. 从一个长度为n的顺序表中，在第i个元素之前插入一个元素需要向后移动（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 63. 在一个单链表head中，若要在指针q所指的结点后面插入一个由指针p所指的结点，则执行（ ）。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p; p->next=q->next; D.p->next=q->next; q->next=p; 64. 若入栈序列为A、B、C、D、E,入栈过程中可以出栈，则不可以是出栈序列（ ）。 A. ABCDE B. BCDEA C. EABCD D. EDCBA 65. 在一个链队列中，假设f和r分别为队首指针和队尾指针，则出队列操作中，下列（ ）语句是必要的。 A. r=f->next B. r=r->next C. f=f->next D. f=r->next 66. 假定一个顺序循环队列的队首队尾指针分别用front和rear表示，则判断队空的条件是（ ）。 A. front=rear B. rear+1=front C. front=0 D. front+1=rear 67. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( D ). A. top=top+1 B. top=top-1 C. top->next=top D. top=top->next 68. 在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（ ）。 A. 2j B. 2j+1 C. 2j-1 D. └j/2┘ 69. 已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是（ ）。 A. 求矩阵第i行非零元素之和 B. 求矩阵第i列非零元素之和 C. 求矩阵第i行第i列元素之和 D. 求矩阵第i行非零元素之和与第i列非零元素之和的差的绝对值 70．n个顶点的连通图至少有（ ）条边。 A. n-1 B. n-2 C. n D. n+1 71. 有一个有序表(6,9,11,12,14,17,21,33,37)，当二分查找值为11的结点时，（ ）次比较后查找成功。 A. 2 B. 3 C. 4 D. 5 72. 从一个具有n个结点的单链表中查找其值等于x的结点,在查找成功时,需平均比较的结点数是( )。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 - 4 - 73. 设哈希表长m=14, 哈希函数H(key)=key。表中已有4个结点： addr(15)=4 ,addr(38)=5, addr(61)=6 ,addr(84)=7 ,其余地址为空。如用线性探测再散列处理冲突，关键字为49的结点的地址是（ ）。 A. 3 B. 5 C. 8 D. 9 74. 对于下图所示的AOV网，不能出现的拓扑排序序列为（ ）。 1 3 5 2 4 A. 12345 B. 12435 C. 24135 D. 21435 75. 数据表A中有10000个记录，如果仅要求求出其中最大的10个元素，则采用（ ）排序最节省时间。 A. 堆 B. 希尔 C. 快速 D. 直接选择 76.数据的最小单位是（ ）。 A. 数据项 B.数据类型 C. 数据元素 D.数据变量 77.下面程序段的时间复杂度是（ ）。 for(i=0;i for(i=0;i c[i][j]+=a[i][k]*b[k][j]; A. O(m*n*t) B. O(m+n+t) C. O(m+n*t) D. O(m*t+n) 78. 一维数组有n个数据元素，则读取第i个数据元素的平均时间复杂度为（ ）。 A. O(n) B. O(nlog2n) C. O(1) D.O(n ) 79.若某链表(不带头结点)中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）的存储方式最节省运算时间。 A. 单链表 B. 循环单链表 C.双链表 D.循环双链表 80.设一个单链表的头指针为head，且该链表没有头结点，则其判空条件是（ ）。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 81.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B建插入结点X的操作序列为（ ）。 A．s->next=p->next ; p->next=s; B. q->next=s; s->next=p; C. p->next=s->next; s->next=p; D. p->next=s; s->next=q; 82、若如栈序列为A、B、C、D、E，入栈过程中可以出栈，则（ ）不可以是出栈序列。 A. ABCDE B. BCDEA C. EABCD D. EDCBA 83、输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到的输出序列为（ ）。 - 5 - A． 2,8,1,4 B. 1,4,8,2 C. 4,2,1,8 D. 2,1,4,8 84、对稀疏矩阵进行压缩存储时为了（ ）。 A. 便于进行矩阵运算 B. 便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度 85、数组A行下标i从1到8，列下标j从1到10，每个元素的长度为3个字节，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。 A． SA+141 B. SA+144 C. SA+222 D. SA+225 86、在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（ ）。 A. 2j B. 2j+1 C. 2j-1 D. └j/2┘ 87、若某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 A. 2n B. n C. n/2 D. n(n-1) 88、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。 A. 第i行非零元素的个数之和 B. 第i列非零元素个数之和 C. 第i行零元素的个数之和 D.第i列零元素个数之和 89、设一组初始记录关键字序列为（13,18,24,35,47,50,62,83,90,115,134），则利用二分查找关键字90需要比较的关键字个数为（ ）。 A. 1 B. 2 C. 3 D. 4 100、下列四种排序中（ ）的空间复杂度最大。 A.快速排序 B. 冒泡排序 C.希尔排序 D.堆排序 1011、下面程序段的时间复杂度为（ ）。 for(i=1,s=0;i for(j=1;j<=i;j++) t=t*j; s=s+t;} A. O(n) B. O(n2) C. O(n3) D. O(n4) 102、以下数据结构中哪个是非线性结构（ ）。 A. 队列 B.栈 C.线性表 D.二叉树 103、设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能的是（ ）。 A. A,B,C,D B. D,C,B,A C. A,C,D,B D. D,A,B,C 104、在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s结点，则执行（ ）。 A. s->next=p->next; p->next=s; B. q->next=s; s->next=p; C. p->next=s->next; s->next=p; D. p->next=s; s->next=p->next; 105、从一个长度为n的顺序表中，删除第i个元素时，需要向前移动（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 106、设顺序循环队列Q[0:M-1]的头指针和尾指针F和R，头指针F总是指向队头元素的前一位置，尾指针总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。 A. R-F B. F-R C. (R-F+M)%M D. (F-R+M)%M 107、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 - 6 - A. front->next=s; front=s; B. s->next=rear;rear=s; C. rear->next=s; rear=s; D. s->nxet=front; front s; 108、在一棵完全二叉树中，若编号为j的结点有右孩子，则其编号为（ ）。 A. 2j B.2j+1 C.2j-1 D. └j/2┘ 109、在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。 A.SA+141 B.SA+144 C.SA+222 D.SA+225 110.以下选项中对广义表LS=(1,2,(3,4),(5,6),7)的正确描述是（ ）。 A.该广义表的数据元素都是单元素数据 B. 该表的长度为6 C.该广义表表头为1，表尾为7 D. 该广义表表头为1，表尾为(2,(3,4),(5,6),7) 111、树最适合用来表示（ ）。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 112、n个结点的二叉树，如果采用二叉链表存储，值非空的链域个数为（ ）。 A.n-1 B.2n-1 C.n+1 D.2n+1 113、如有18个元素的有序表存放在一维数组A[19]中，第一个元素存放在A[1]中，先进行二分查找，则查找A[3]的比较序列的下标依次为（ ）。 A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D.9,4,2,3 114、已知10个数据元素（54,28,16,34,73,62,95,60,26,43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是（ ）。 A. 2 B. 3 C. 4 D. 5 115、时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。 A. 堆排序 B.冒泡排序 C. 希尔排序 D.快速排序 二、判断题 线性表的长度是线性表所占用的存储空间的大小。( ) 在顺序表中取出第i个元素所花费的时间与i成正比。( ) 在栈为空的情况下，不能做出栈操作，否则产生下溢出。( ) 在对链队列做出队操作时，不会改变front指针的值。( ) 二叉树中叶子结点就是二叉树中没有左右子树的结点。( ) 有向图用邻接矩阵表示后，结点i的出度等于第i行中非0且非∞的元素个数。( ) 对B树中任一非叶子结点中的某关键字k，比k小的最大关键字和比k大的最小关键字一定都在叶子结点中。( ) 8. 对任意一个图，从它的某个结点出发进行一次DFS或BFS可访问到该图的每个结点。 ( ) 9. 对一个堆，无论按二叉树层次遍历还是先序遍历，都不一定能得到有序序列。( ) 10. 任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。( ) 11. 线性表采用链表方式和顺序方式存储，执行插入和删除运算的时间复杂度都是O(n)，因 而两种存储方式的插入、存储运算所花费的时间相同。 12. 在双循环链表中，任意一结点的后继指针均指向其逻辑后继。 13. 在对链队列做出队操作时，不会改变front指针的值。 14. 已知一棵树的先序序列和后序序列，一定能构造出该树。 15. 若一棵二叉树的任一非叶结点的度为2，则该二叉树为满二叉树。 16. 有向图用邻接矩阵表示后，顶点i 的入度等于邻接矩阵中第i列的元素个数。 - 7 - 1. 2. 3. 4. 5. 6. 7. 17. 18. 19. 20. 所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。 在一个根最大堆中，最大元素在根，最小元素在最低层。 快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 9阶B树中，除根以外的任一结点中的关键字个数不小于4。 21. 在顺序表中取出第i个元素所花费的时间与i成正比。 22. 在栈为空的情况下，不能做出栈操作，否则产生下溢出。 23. 在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为(Rear – Front)。 24. 若一棵二叉树的任一非叶结点的度为2，则该二叉树为满二叉树。 25. 已知一棵树的先序序列和后序序列，一定能构造出该树。向二叉排序树中插入一个结点， 所需比较的次数可能大于此二叉排序树的高度。 26. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条。 27. 9阶B树中，除根以外的任一个非叶子结点中的关键字数目均在5～9之间。 28. 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根 结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。 29. 给定结点数的平衡二叉树的高度是唯一的。 30.理想情况下，在散列表中查找一个元素的时间复杂度为O(1)。 31、线性表的长度是线性表所占用的存储空间的大小。 （ ） 32、在带头结点的循环单链表中，任一结点的后继指针均不空。 （） 33、栈和队列都是运算受限的线性表。 （ ） 34、数组（矩阵）是一种没有插入与删除操作的非线性结构。（ ） 35、广义表的长度指广义表中的原子个数。（ ） 36、若某二叉树的叶子结点数为1，则其先序遍历序列和后序遍历序列一定相反。 （） 37、完全二叉树就是满二叉树。（ ） 38、就平均查找长度而言，分块查找最小，二分查找次之，顺序查找最大。（） 39、在m阶B-树中，所有非终端结点至少包含┌m/2┐个结点。（） 40、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费时间多。 （ ） 41．顺序存储方式只能用于存储线性结构。（ ） 42．数据的逻辑结构与存储结构都是依赖于计算机的。 ( ) 43. 非空线性表中任意一个数据元素都有且只有一个直接后继元素。 （ ） 44.在顺序表中取出第i个数据元素所花费的时间与i成正比。 （ ） 45. 二维数组是它的数据元素为线性表的线性表。 （ ） 46.广义表的长度指广义表中的原子个数。（ ） 47. 完全二叉树就是满二叉树。 （ ） 48. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ ） 49.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费时间多。 （ ） 50.对一个堆，无论按二叉树层次遍历还是先序遍历，都不一定能得到有序序列。（ ） 51. 线性表的唯一存储方式是链表。（ ） 52. 线性表的长度是线性表所占用存储空间的大小。 （ ） 53. 栈和队列都是运算受限的线性表。 （ ） 54.在栈满的情况下不能作进栈操作，否则产生上溢。 （ ） 55.数组可看成是对线性结构的一种推广，因此可以对它进行插入、删除操作。 （ ） 56. 二叉树只能用二叉链表来存储。 （ ） - 8 - 57.将一棵树转换成二叉树后，根结点没有左子树。 （ ） 58. 有向图用邻接矩阵表示，顶点i的出度等于第i行中非0且非∞的元素个数。 （ ） 59. 对任意一个图，从它的某顶点出发进行一次深度优先或广度优先搜索，可访问到图的每一个顶点。 （ ） 60. 二叉排序树查找和二分查找的时间性能相同。 （ ） 三、填空题。 1. 数据元素之间存在的相互关系称为 ，分为 和 两大类。 2. 计算机之内的数据关系称为 结构，基本方法为 方法、 方法、 方法和 方法。 3.与后缀表达式3 5 2-7*+等价的中缀表达式为 。 4.树转换成的二叉树，其根结点的 子树一定为空。 5、评价算法的优劣，首先应该是算法的 ；此外除要求算法易于理解、编码、调试外，是以算法的 和 来衡量算法的优劣的。 6、为了能有效地应用散列查找技术，必须解决的两个问题是 和 。 7、多维数组一般采用 存储方法存储数据；广义表一般采用 方式存储。 8设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 9.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。 10设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。 11设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。 12设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 13设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 14设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 15设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 16中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。 17快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。 18设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。 19设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。 20设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。 - 9 - 四、综合题 1. 已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树,并写出后根序列。 2. 给定权值7，18，3，22，5，25，12，8，构造相应的哈夫曼树，并求这棵哈夫曼树 的带权路径长度WPL。 3. 已知散列函数为H(K)=K mod 13,关键码序列为25，37，52，43，84，99，120，15， 26，11，70，82，1，采用拉链法处理冲突，画出构造的散列表，并计算查找成功的平均查找长度。 4. 设有无向图G（如右图所示）， i、写出采用邻接矩阵存储的表现形式； ii、按照其存储结构给出用普里姆算法构造最小生成树的过程 iii、写出该图的深度优先和广度优先遍历的序列。 5. 已知一棵二叉树的前序遍历的结果序列是ABDGEHCFI，中 序遍历的结果是GDBHEAFIC，试写出这棵二叉树的后序遍历结果。(要求分析过程) 6. 已知某系统在通信联络中只可能出现9种字符，其频率分别为0.05，0.20，0.07，0.08， 0.14，0.23，0.02，0.11，0.10设它的权值w＝（5，20，7，8，14，23，2，11，10），试设计哈夫曼编码。 7. 已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快 速排序的每一次划分结果。 8. 已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,…，m－1 其中 h1(key)=key+1 回答下列问题： （1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 9. 已知一棵二叉树的前序遍历的结果序列是ABDEGIKCFHJL，中序遍历的结果是DBEIKGACFJLH，试写出这棵二叉树的后序遍历结果。 10. 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单 选择排序和第4趟直接插入排序后的结果。 11. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8， 27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 12. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; - 10 - E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 13. 多维数组、广义表一般采用什么存储方式？为什么？ 14. 队列可以用循环单链表来实现，故可以只设置一个头指针或尾指针。请分析对于循环单链表实现的队列，用哪种方案更合适。 15、存储结构的设计与什么因素有关，请举例说明。 16、说明任意三个结点可构造多少种形态的树，多少种形态的二叉树，图示之。 17、二叉树与树在概念上是相同的吗？为什么？ 18、什么是散列表？实际上其查找时间性能为O(1)吗？为什么？ 19.已知二叉树的中序遍历序列为CDBAEGF,后序遍历序列为DCBGFEA,请画出该二叉树。 20. 若一篇文档有以下字符：A、B、C、D、E、F，各字符在文档中出现的概率依次为4,5,6,7,10,12。请构建以各字符为叶子结点的Huffman树，并写出各字符的Huffman编码。（构建时按左小右大、左0右1的规则进行） 21. 一组待排序的记录关键字为(68,45,21,82,34,16,56), 则 (1) 利用直接插入排序第一、第二趟的变化序列。 (2) 利用快速排序第一趟的变化序列。 22. 已知如下无向网络的邻接矩阵（其权值为整型数据） (1)写出从顶点4出发的深度优先搜索序列、从顶点1出发的广度优先搜索序列。 (2) 用prim算法思想求最小生成树，要求画出生成过程。 1 2 3 4 5 6 1 ∞ 3 1 ∞ ∞ ∞ 2 3 ∞ 2 4 ∞ ∞ 3 1 2 ∞ 2 ∞ ∞ 4 ∞ 4 2 ∞ 3 4 5 ∞ ∞ ∞ 3 ∞ 1 6 ∞ ∞ ∞ 4 1 ∞ 23、给定叶子结点（1,3,5,6,7,8），构造哈夫曼树。 24、已知如下有向图的邻接矩阵： 0 10 ∞ 30 100 ∞ 0 50 ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ 20 0 60 ∞ ∞ ∞ ∞ 0 （1）写出从顶点1出发的DFS、BFS序列。 （2）求顶点1到其余顶点的最短路径。 25、已知一组初始的关键字序列为（46,79,56,38,40,84）,则写出利用快速排序得到的第一趟的变化序列。 26、已知关键字序列为(75,33,52,41,12,88,66,27),哈希表长为10，哈希函数为： H(K)=K%7，解决冲突用线性探测再散列法，构造哈希表，求等概率条件下查找成功的平均查找长度。 27、一棵二叉树的先序遍历序列为abdefcg，中序遍历序列为dfebagc，试画出该二叉树。 28、若一篇文档有以下字符：A、B、C、D、E、F,各字符在文档中出现的概率依次为4,5,7,8,10,12， - 11 - 请构造一个字符为叶子结点的Huffman树，并写出各字符的Huffman编码，（构造时按左小右大、左0右1的规则进行）。 29、已知一组初始记录关键字序列为（55,63,44,38,75,80,31）,则写出 （1）利用快速排序得到第一趟的变化序列。 （2）用堆排序建立起来的第一个大根堆。 30、已知如下无向网的邻接矩阵，其权值为整形数据。 ∞ 6 1 5 ∞ ∞ 6 ∞ 5 ∞ 3 ∞ 1 5 ∞ 5 6 4 5 ∞ 5 ∞ ∞ 2 ∞ 3 6 ∞ ∞ 6 ∞ ∞ 4 2 6 ∞ （1） 写出从顶点4出发的DFS、BFS序列。 （2） 写出使用Prim 算法构造最小生成树的过程。 31. 有下列图的数据结构： V = {0，1，2，3，4，5，6，7，8，9}； E = {（0，1），（0，3），（1，2），（1，7），（2，8），（3，4），（3 ，5），（5，6）， （5，8），（5，9），（6，7），（7，8），（8，9）} （1）写出它的邻接表； （2）根据邻接表存储分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 五、程序题 1、试编写在带头结点的单链表上实现线性表操作LENGTH（L）的算法，并将长度写入头结点的数据域中。 typedef struct node{ int data; struct node* next; }linklist; int length(linklist* head) 1分 { linklist*p; int n=0; p=head->next; 1分 while(p!=NULL) 2分 { p=p->next; n++; } 4分 head->data=n; 1分 return n; 1分 } 2、已知DBF（int j）是连通图的遍历算法。非连通图的遍历算法如下，请在此基础上修改算法，使该算法具有求出非连通图中有多少个连通分量的功能. TRAVER ( ) - 12 - { int j; for(j=0;j { DFS(j); printf(“comp end\\n”); } } int TRAVER ( ) { int j; int k=0; 2分 for(j=0;j { DFS(j); printf(“comp end\\n”); k++; 4分 } return k; 2分 } 1分 } 3.如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=______________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K<[mid].key) _______________________; //在左子表上继续查找 } return -1; //查找失败，返回-1 } 4. LinkList mynote(LinkList L) else __________________;//在右子表上继续查找 - 13 - {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； 5. 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data) { item=BST->data;//查找成功 return _____（1）____; } else if(item return Find(_____（2）_______,item); else return Find(_______（3）______,item); }//if } 6.假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。 - 14 - 7.设有一二叉链表T，编写递归算法，计算二叉链表中叶子的数目； 8.求带头结点的单链表head中结点的值等于给定值X的结点数目。 int count(linklist* head,datatype x) 1分 { linklist*p=head->next; 1分 int n=0; 1分 while(p!=NULL) 2分 { if(p->data==x) n++; 2分 p=p->next; 2分 } return n; 1分 } 9、以二叉链表为存储结构，试编写算法求二叉树叶子结点的数目。 int leafnum(bitree *t) 1分 { int num1,num2; if(t==NULL) return 0; 1分 else if(t->lchild==NULL&& t->rchild==NULL) return 1; 2分 else { num1=leafnum(t->lchild); 2分 num2=leafnum(t->rchild); 2分 return(num1+num2); 2分 } } /* leafnum*/ - 15 - 10.实现在带头结点的单链表尾部插入新元素X的操作。 1 int instail(linklist*head,datatype x) 1分 {linklist *p,*s; p=head; 1分 s=(linklist*)malloc(sizeof(linklist)); 1分 if(s==NULL) {printf(“malloc failure!”); return NULL;} s->data=x; 1分 s->next=NULL; 1分 while(p->next!=NULL) 1分 p=p->next; 2分 p->next=s; 2分 return TRUE; } 11.以二叉链表为存储结构，试编写求二叉树高度的算法。 int depth(bitree* t) 1分 { int dep1,dep2; if(t==NULL) return 0; 1分 else { dep1=depth(t->lchild); 2分 dep2=depth(t->rchild); 2分 if(dep1>dep2) return(dep1+1) ; 2分 else return(dep2+1); 2分 } } - 16 - 12设计一个求结点x在二叉树中的双亲结点算法。 13. 设计在链式存储结构上建立一棵二叉树的算法。 14. 设计判断一棵二叉树是否是二叉排序树的算法。 15.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。 15. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链 式存储结构表示。 - 17 - 17设计在单链表中删除值相同的多余结点的算法。 18.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。 struct record{int key; int others;}; int hashsqsearch(struct record hashtable[ ],int k) { int i,j; j=i=k % p; while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); } 19.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。 typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) { if (t==0 ) return(0);else while (t!=0) if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; } 20.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 - 18 -