2024年6月13日发(作者：)
《数据结构》题库及答案
一、选择题
1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。
a. 随机存储； b.顺序存储； c. 索引存取； d. HASH存取
2．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是 。
a. edcba; b. decba; c. dceab;
3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。
a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; ,2,4,1
4．在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s，则执行的操作是 。
a. s->nxet=p->next; p->next=s;
b.
c.
|
p->next=s->next; s->next=p;
d. q->next=s; s->next=p;
e. p->next=s; s->next=q;
5．设有两个串p,q，求q在p中首次出现的位置的运算称作 。
a.联接 b.模式匹配 c.求子串 d.求串长
6．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j
的范围从1到10，则存放M至少需要 个字节。
a. 90
7．在线索二叉树中，结点p没有左子树的充要条件是 。
a. p->lch==NULL
b. p->ltag==1
c.
d.
·
p->ltag==1且p->lch=NULL
e. 以上都不对
8．在栈操作中，输入序列为（A，B，C，D），不可能得到的输出序列为：______
A、（A，B，C，D） B、（D，C，B，A）
C、（A，C，D，B） D、（C，A，B，D）
9．已知某二叉树的后序序列是dabec，中序序列是debac，则它的先序序列是 。
A、acbed B、decab C、deabc D、cedba
10．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组(n-1)/2]
中，对任一上三角部分元素
a
ij
(i
j)
，在一维数组B的存放位置是 。
a
11
A
a
21
a
n1
A、
/
a
22
a
n2
a
nn
i(i1)j(j1)
j1
B、
i1
22
j(j1)
i(i1)
i
D、
j
2
2
C、
11． 图G中有n个顶点，n-1条边，那么图G一定是一棵树吗 。
A、 一定是 B、一定不是 C、不一定
12． 用某种排序方法对关键字序列{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况
如下：
① {25，84，21，47，15，27，68，35，20}
② {20，15，21，25，47，27，68，35，84}
③ {15，20，21，25，35，27，47，68，84}
④ {15，20，21，25，27，35，47，68，84}
则所采用的排序方法是 。
A、 快速排序 B、希尔排序
@
C、归并排序 D、选择排序
13．表达式a*(b+c)-d的后缀表示式是 。
a. abcd-*+; b. abc+*d-; c. abc*+d-; d. -*a+bcd;
14．在双向循环链表中的结点P之后插入结点S的操作是 。
a. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
b. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
c. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
d. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
15．如下图所示循环队列，其中的数据元素个数是
<
m-1
…
…
0
1
《
串是一种特殊的线性表，其特殊性体现在 。
a. 可以顺序存储
b. 数据元素是一个字符
c.
d.
e.
可以链接存储
<
数据元素可以是多个字符
17． 数组A中，每个元素A[i][j]的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始
连续存放在存储器内，存放该数组的单元数是 。
a. 80
b. 100
c. 240
d. 270
18．已知某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历的结点访问顺序序列
是 。
a. bdgcefha
b. gdbecfha
c.
d.
e.
bdgaechf
；
gdbehfca
19．线索二叉树是一种 结构。
a. 逻辑
b. 逻辑和存储
c. 物理
d. 线性
20．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
a. 1/2
b. 1
c.
d.
e.
2
：
3
21．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所
在的块时，则每块应分为 个元素的块时，查找效率最佳。
a. 10
b. 25
c. 6
d. 625
22．一个栈的输入序列是12345，则栈的不可能输出序列是 。
a. 54321
b. 45321
c.
d.
e.
43512
/
12345
23． 完全二叉树一定是满二叉树吗 。
a. 一定是
b. 不是
c. 不一定
24．线性表采用链式存储结构时其地址 。
a. 必须是连续的
b. 部分地址必须是连续的
c.
一定是不连续的
d. 连续不连续都可以
。
25． 具有线性结构的数据结构是 。
a. 树
b. 图
c. 广义表
d. 栈
26．下图为顺序队列的初始情况，设a, b, c相继出队列，e, f相继入队列，则指针和分别为 。
=4
5
4
d
c
=0
b
a
3
2
1
0
a. 2,5
b. 3,5
c.
二、填空题
3,6
d. 4,6
1．设n行n列的下三角阵A已经压缩存储到一维数组S[0..
在S中的存储位置是 。
/
n(n1)
2
1
]中，若按行序为主序存储，则A[i][j]对应的
2．广义表（（a），（（b），c），（（（d））））的长度是 ，深度是 。
3．深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右的次序给结
点编号（从1开始），则编号最小的叶子结点的编号是 。
4．根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点v1出发进行搜索，所得到的顶点遍历序列
是 。
:
0
1
2
3
V
1
V
2
V
3
]
NULL
NULL
2
1
3 NULL
3
[
1 3 NULL
V
4
4 V
5
图2
5．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的元素时，需
要经过 次比较就找到。
6．_____________是数据的最小单位。
7．在双向链表中，每个结点有两个指针域，一个是指向_____________,另一个指向_________。
8．设栈ST用顺序存储结构表示，则栈ST为空的条件是____________________。
9．两个串相等的充分必要条件是_____________________和对应位置上的字符相等。
10．对于深度为h的二叉树至多有___________个结点。
11．将一个A
15
15
的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为__________。
、
三、算法应用题
1．数据集{4，5，6，7，10，12，18}为结点权值构造Huffman树，请给出构造所得的Huffman树，并求其带权
路径长度。
2．假设一棵二叉树的先序序列是EBADCFHGIKJ，中序序列是ABCDEFGHIJK。请画出该二叉树。
3．已知一颗二叉排序树如下图所示，若依次删除93、19、87、48结点，试分别画出每删除一个结点后得到的二
叉排序树。
4．已知关键字序列{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key%13，和
开放地址法的线性探测再散列方法解决冲突，已知其装填因子
求其查找成功时的平均查找长度。
5．画出和下列已知序列对应的森林F:
森林的先序遍历序列是：ABCDEFGHIJKL；
?
2
，试对该关键字序列构造哈希表，并
3
森林的中序遍历序列是：CBEFDGAJIKLH。
6．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为, , , , , , , 。请给这8个字母设计哈
夫曼编码。
7．对下图所示的无向带权图，
V
2
6
5
6
V
5
V
1
$
5
5
4
V
4
2
① 给出其邻接矩阵，并按Prim算法求其最小生成树；
② 给出其邻接表，并按Kruskal算法求其最小生成树。
V
3
3
6
V
6
8．我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
试问：
① n=7时在最好情况下需进行多少次比较请说明理由。
② 对n=7给出一个最好情况的初始排列实例。
:
9．下列算法为斐波那契查找算法：
int FibSearch (SqList r, KeyType k)
{
j=1;
while (fib(j) mid=n-fib(j-1)+1; ey): found=true; break; case (k if (!f2) mid=0; else{ mid=mid-f2; t=f1-f2; f1=f2; f2=t; } break; 、 case (k>r[mid].key): if (f1==1) mid=0; else { mid=mid+f2; f1=f1-f2; f2=f2-f1; } break; } if found return mid; else return 0; } A(a 1 ,a 2 ,,a m ),B(b 62 1 ,b E b n ) A,B C C(a 1 ,b 1 ,a 2 ,b 2 ,,a m ,b m ,b m1 ,,b n ) mn 2 ,, V C(a 1 ,b 1 ,a 2 ,b 2 ,,a 2 ,a n1 ,,a) m V CC AB mn 1,2,,n p 1 ,p 2 , ,p n ijk n 7 A, a B =2 n ,b … m a 1 =6 a n 4 =1 10 ； B 25 F V 1 a 2 =4 19 a 3 =5 10 V 4 V 3 a 5 =1 9 V 5 6 A 18 a 12 D 8 =7 C a 9 =4 V 8 [ 13 V 9 H a 11 =4 G 7 K a 4 6 =2 p j p k p i n 0 n 1 n 0 (k1)n 1 1 i(i1) j 2 h 1 J 2 | | 2 3 》 $ ） % ~ # ASL succ 60 1 40 1 0 ^ B 0 G $ I 28 1 32 19 21 0 C 11 E F 17 。 1 J ? 1 0 { 10 0 5 < 6 2 3 》 12143113113223 100 1 A 12 0 12 H K L · % 1 V (a) V 2 V 56 1 1 1 5 1 4 23 NULL 6 ASL succ 234753 7 .8 6 5 1) V 13 V 1 (1 0 6 6 V 1 a =9 V 1 2 ' ~ a=16 5 a 10 =2 47 20 } V 1 5 1 6 《 V 5 1 1 0 2 4 NULL 1 1 1 > 8 V 2 18 V 4 V 4 | V 2 V 9 V 2 5 V | 1 5 V 4 5 5 5 V V V V 15 242 · 3 NULL V 5 5 a5 a=7 2 2 =4 0 8 5 V 24 V 3 V 3 . V 3 5 V V 33 ￥ a 11 =4 … 3 3 a 5 =1 2 16 2 V 32 V 5 0 115 20 NULL 3 V 8 3 3 6 2 3 6 2 4 a 3 =5 4 6 4 V 3 。 ( 6 4 2 4 3 1 2 5 NULL 6 4 4 V 5 V @ V 6 V V 5 6 V 6 =4 6 4 6 . > a 9 6 V 12 5 15 6 17 V 6 19 V 5 . 6 V 6 7 2 10 — 3 V 6 V 5 6 V 6 5 ` V 4 (a) c） （ (b) (b) ! 2 > 4 6 14 | V 1 V 1 6 5 6 5 V 1 6 5 1 V 1 1 V 1 1 6 1 5 V 1 6 5 6 5 V 2 5 V 2 5 5 V 4 5 V 4 1 5 V 4 V 2 ) vertex[v].firstadj; V 2 1 1 V 3 V 3 V 4 V 7 a=2 V 2 5 V 】 < 3 a=6 a=1 a=9 V V V 147 10 while(p) 242 3 3 5 5 5 — 5 2 V 3 > < 3 2 6 4 V V … 33 6 4 { 3 2 V V V 15 3 2 3 V 5 2 6 4 ？ | V 5 】 6 6 a 8 =7 4 6 6 4 w=p-> adjvex; V 5 6 V 6 a 5 =1 a=4 V 5 6 # 11 V 8 。 a=5 if (!visited[w]) dfs(g,w); V V V 3 5 (e) 6 66 (d) V 3 6 ： p=p->next; (f) a 9 =4 (e) (d) a 6 =2 V 6 } V 4 } … ` — 单链表存储结构： typedef struct Lnode *LinkList; 4．解答：本题涉及的存储结构描述如下： typedef struct Lnode { DataType data; LinkList next; }Lnode,*LinkList; void merge_two_asceding_linklist_to_one_desceding_linklist (LinkList& lc, LinkList la,lb) @ pa=la->next; { pb=lb->next; lc=la; pc=lc; pc->next=NULL; while （ pa && pb ） { > if (pa->data < pb->data) { } else { u=pb->next; pb->next=pc->next; u=pa->next; pa->next=pc->next; pc->next=pa; pa=u; ￥ } } pc->next=pb; pb=u; while (pa ) { u=pa->next; pa->next=pc->next; pc->next=pa; pa=u; 、 } while (pb ) { } delete(lb) } 5．解答：本题涉及的存储结构描述如下： 顺序存储结构： const maxsize=100; typedef int ElemType; typedef struct{ ElemType r[maxsize+1]; int length;//实际长度 }SqList; Void inert_x_into(SqList& va, int x) { j=; while ( (x<[j])&&(j>=0) ) { } [j+1]=x; =+1; } 五、简答题 1．存储图： [j+1]=[j]; j--; u=pb->next; pb->next=pc->next; pc->next=pb; pb=u; 1 ∧ 0 a 2．树： a b c 二叉树： 1 1 1 ∧ 1 ∧ 0 f ∧ 0 d 0 e 0 b 1 ∧ 0 c 1 ∧ a b c a a a b a b b c a b c c c b 六、证明题 1．证明：反证法。 设存在 ijk 使得 p j p k p i 。 则①由 ijk 得出栈序列 p i ,p j ,p k ； ②由 p j p k p i 得知入栈序列为 p j ,p k ,p i ； c 由①知 p i 最先出栈，则由②知出栈的序列将是 p i ,p k ,p j 。此出栈序列与由①得到的出栈序列矛盾。因此假 设错误。从而若借助栈由输入序列 1,2,,n 得到的输出序列为 p 1 ,p 2 , ,p n (它是输入序列的一个排列)，则 在输出序列中不可能存在 ijk 使得 p j p k p i 。 证毕 2．证明：设总结点数为 n ，则： nn 0 n 1 ①； 又该满k叉树上的每个结点出根之外都一个分支进入，这些分支是由非叶子结点产生的，因此有： nkn 1 1 ②； 由①和②得： n 0 n 1 kn 1 1 n 0 kn 1 1n 1 (k1)n 1 1 证毕
发布评论