一、选择题
1. 线性表的顺序存储结构是一种 _的存储结构，线性表的链式存储结构是一种—的存储结构。
a.
随机存储：b.顺序存储：c.索引存取：d. HASH存取
2. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输岀序列是 _________ °
a. edcba; b・ decba; c. dceab;
3. 一个队列的入队序列是1, 2, 3, 4,则队列的输出序列是 ___________________
a. 43,2,1； b・ 1,23,4; c. 143,2;
,2,4,1
4. 在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s,则执行的操作是 ________ o
a. b. c
p->next=s->next; s->next=p; s->nxet=p->next; p->next=s;
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没有左子树的充要条件是 ________ o
a.
p->lch==NULL
b・ p->ltag==l
C・
a p->ltag==l 且 p->lch=NULL e.以上都不对
&在栈操作中，输入序列为(A, B. C, D),不可能得到的输出序列为： _________________
A、(A, B, C, D) C、(A, C, D, B)
B、(D, C, B, A) D. (C, A, B, D)
9. ________________________________________________________________________ 已知某二叉树的后序序列是dabec,中序序列是debac,则它的先序序列是 ______________________________________。
A、 acbed B> decab C、 deabc D^ cedba 10・设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分(见下图)按行序存放在一维数组B[l..n(n-l)/2]
中，对任一上三角部分元素在一维数组B的存放位置是 __________________
11
nl nn
A、 诧一1) +丿一1
B
2
、
□・c图D、
G中有
n个顶
A则所采用的排序方法是、一定是 B、一47, 15. 27, 68, 35, 20｝进行排序时，元素序列的变化情况泄不是
12.用某种
排序 方法 对关 键字 序列
{25, 84, 21,
如下：
① {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}
15.如下C.A归并排图所示速排序a.、快
p->nex s
B、希
尔排序
序循环队
b. p・>n exts
C、不_定
a. 可以顺序存储 b. 数据元素是一个字符 C・ 可以链接存储 d. <
e.
数据元素可以是多个字符
17. 数组A中，每个元素A[i][j]的长度是3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始 连续存放在存储器内，存放该数组的单元数是 ______ 。
a. b. c. d.
80 100 240 270
18. 已知某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,则英后序遍历的结点访问顺序序列 是 ___________ a. bdgcefha b. gdbecfha C・ bdgaechf d.
e.
gdbehfca
19. ___________________________ 线索二叉树是一种 结构。 a. 逻辑 b. 逻辑和存储 c. 物理 d. 线性
20. 在一个有向图中，所有顶点的入度之和等于所有顶点的岀度之和的 ____________ 倍。
a. V2 b・1 c. 2
d・: e. 3
21. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确左元素所 在的块时，则每块应分为 ___________ 个元素的块时，查找效率最佳。
a・10 b・25
c. 6
d. a. b. c. d. e.
625 54321 45321 43512
)
22. 一个栈的输入序列是12345,则栈的不可能输岀序列是 _______________
12345
23. ________________________________ 完全二叉树一泄是满二叉树吗
a. b.
一定是 不是
C.不一定
24. ____________________________________ 线性表釆用链式存储结构时其地址
a.必须是连续的 b. c. d.
部分地址必须是连续的 一左是不连续的 连续不连续都可以
25. 具有线性结构的数据结构是 ___________ o
a. b. c. d.
树 图 广义表 栈
26. 下图为顺序队列的初始情况，设az b,c相继出队列，巳f相继入队列，则指针和分别为
a. 2,5 b. 3,5 c. d.
3,6 4,6
二、填空题
1•设n行n列的下三角阵A已经压缩存储到一维数组S[0••畔-1]中，若按行序为主序存储，则A[i][j]对应的
在S中的存储位置是 ______________
2. 广义表((a), ((b), c), (((d))))的长度是 _____________________ ,深度是 ____________ 。
3. 深度为k的完全二叉树至少有 ______ 个结点，至多有 _________ 个结点，若按自上而下，从左到右的次序给结
点编号(从1开始)，则编号最小的叶子结点的编号是 _________ °
4. 根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点vl岀发进行搜索，所得到的顶点遍历序列
是 _______________ J
图2
5. 有一个有序表为｛1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100｝,当二分査找值为82的元素时，需 要经过 ____ 次比较就找到。
6. ____________ 是数据的最小单位。
7. 在双向链表中，每个结点有两个指针域，一个是指向 _______________ 另一个指向 _________ 。 &设栈ST用顺序存储结构表示，则栈ST为空的条件是 _______________________ o 9. 两个串相等的充分必要条件是 ______________________ 和对应位置上的字符相等。 10. 对于深度为h的二叉树至多有 ___________ 个结点。
□・将一个A[15][15]的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为 ____________ °
三. 算法应用题
1.数据集｛4, 5, 6, 7, 10, 12, 18｝为结点权值构造Huffman树，请给岀构造所得的Huffman树，并求苴带权
路径长度。
2•假设一棵二叉树的先序序列是EBADCFHGIKJ.中序序列是ABCDEFGHIJIG请画出该二叉树。
3.已知一颗二叉排序树如下图所示，若依次删除93、19、87、48结点，试分别画出每删除一个结点后得到的二 叉排序树。
87
19
4・已知关键字序列{19, 01 > 23, 14, 55, 20, 84, 27, 68, 11, 10, 77},采用哈希函数：H(key)=key%13> 和 2
开放地址法的线性探测再散列方法解决冲突，已知英装填因子« = -,试对该关键字序列构造哈希表，并 3
求其査找成功时的平均査找长度。 5.画岀和下列已知序列对应的森林F:
森林的先序遍历序列是：ABCDEFGHIJKL；
森林的中序遍历序列是：CBEFDGAJIKLHo
6 •假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为……… 请给这8个字母设计哈
夫曼编码。
7.对下图所示的无向带权图，
① 给岀其邻接矩阵，并按Prim算法求苴最小生成树: ② 给出其邻接表，并按Kruskal算法求其最小生成树。
&我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。 试问：
① n=7时在最好情况下需进行多少次比较请说明理由。 ② 对n=7给岀一个最好情况的初始排列实例。 9.下列算法为斐波那契查找算法：
int FibSearch (SqList r, KeyType k) {
j=l；
while (fib(j) else{ mid=mid-f2; t=fl-f2; fl=f2; f2=t;} break; case (k>r[mid].key): if (fl==l) mid=O; else { mid=mid+f2; fl=fl-f2; f2=f2-fl;} break; if found return mid; else return 0; } A = (q,d C = (a^b^a 19 Pj Y pk Y 62 A、B C C =(5片皿2上2,…上皿上卄―小…、b) m 12 Pi I)® + 1 恥厶心e 2 NU 4 5 NULL 小b)(b) (c) vertexlv p 二 p・〉n exx- (d) (f) 4・解答：本题涉及的存储结构描述如下: 单链表存储结构： typedef struct Lnode *LinkList; typedef struct Lnode DataType data; LinkList next; jLnode/LinkList; void merge_two_ascedingjinklist_to_one_desceding_linklist (LinkList& Ic, LinkList lajb) { pa=la->n ext; pb=lb->n ext; lc=la; pc=lc; pc->next=NULL; while ( pa && pb ) { if (pa->data < pb->data) > { u=pa next; pa・>n ext=pc->next; pc->next=pa; pa=u; } else { u=pb->next; pb->next=pc- >n ext; Y pc->next=pb; pb 二 u; } } while (pa ) { u=pa->n ext; pa・>n ext=pc->next; pc・>n ext=pa; pa=u; } while (pb ) { u=pb->next; pb->next=pc->n ext; pc・>n ext=pb; pb=u; } delete(lb) } 5.解答：本题涉及的存储结构描述如下: 顺序存储结构： const maxsize=100; typedef int ElemType; typedef struct{ ElemType r[maxsize+l]; int length;//实际长度 }SqList; Void inert_xJnto(SqList& va, int x) { j=; while ((x<[j])&&(j>=0)) { U+1]=U]; j-; } [j+l]=X； =+l; 五.简答题 1. 存储图： 2 •树: 二叉树: 六、证明题 1. 证明：反证法。 设存在，Y j Yk使得门Y Pk Y Pi。 贝IJ①由jYk得出栈序列门，厂，几； ②由PjY ［兀Y H得知入栈序列为Pj、Pk , Pi ； 由①知戸最先出栈，则由②知出栈的序列将是□，几，厂。此岀栈序列与由①得到的岀栈序列矛盾。因此假 设错误。从而若借助栈由输入序列1,2,…,”得到的输出序列为门，“2,…,卩”（它是输入序列的一个排列），则 在输出序列中不可能存在iY JYk使得厂• Y几VP, ° 证毕 2. 证明：设总结点数为”，贝IJ: n = n0 + ①： 又该满k叉树上的每个结点出根之外都一个分支进入，这些分支是由非叶子结点产生的，因此有： n = k叫+1 ②： 由①和②得： 川（）+ 坷=kn{ +1 n0 = k 叫 +1 _ n{ = （£ _ l）q +1 证毕 因篇幅问题不能全部显示，请点此查看更多更全内容