数据结构习题集和答案

1、第 1 章 绪论1、填空题1.常见的数据结构有集合，_线性 结构， 树形结构， 图形 结构等四种。2.常见的结构有 顺序 结构， 链式 结构等两种。3.数据的基本是_数据元素，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类， 线性结构和 非线性结构。2、选择题1. 算法的计算量的大小称为计算的（B）。A效率B. 复杂性C. 现实性D. 难度2. 算法的时间复杂度取决于（C ）A问题的规模对B. 待处理数据的初态C. A 和 BD. 以上都不3.计算机算法指的是（1）（c），它必须具备（2）（B） 这三个特性。(1) A计算方法调度方法B.

2、排序方法C. 解决问题的步骤序列D.(2) A可执行性、可移植性、可扩充性C. 确定性、有穷性、稳定性B. 可执行性、确定性、有穷性D. 易读性、稳定性、安全性4. 下面关于算法说法错误的是（A算法最终必须由计算机程序实现D ）B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的3、应用题1、给出以下算法的时间复杂度.void fun(int n)int i=1,k=100;while(i<n)k=k+1;i=i+2;时间复杂度为O（n）。2、给出以下算法的时间复杂度.void fun2(int n)int i=1,k=10

3、0;while(i<n)i=i*10;k=k+1;时间复杂度为O（log n）。第 2 章 线性表1、填空题1. 线性表按照一种是链表。结构不同主要有两种实现方式，一种是 顺序_表，另2.顺序表采用 随机机制对数据元素进行。3.若在单链表结点 p 的后面一个新的结点 s，则其操作序列为:s->next=p->next；p->next=s；4.在单向链表中，若要删除某个结点 p，一般要找到 p 的前趋 结点，才能实现该操作。2、选择题1. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是A。(A)n(B)2n1(C)2n(D)n-1一个新结点 s，其操作

4、为2. 在单链表中，如果在结点 p 之后（A）s->next=p->next; p->next=s;A。（B）p->next=s;（C）s->next=p;（D）p->next=s;s->next=p->next; p->next=s->next;s->next=p;3.若长度为 n 的线性表采用顺序结构，在其第 i 个位置删除一个元素的算法的平均时间复杂度为(C)。(1in)C.O(n)DO(n2)AO(0)BO(1)4. 若长度为 n 的线性表采用顺序结构，在其第 i 个位置前一个新元素需要移动的元素个数为(B)。(1in+

5、1)An-iBn-i+1C. iDn-i-13、题1.线性表中每一个元素都有一个前驱和一个后继。（ ×）2. 在顺序结构中，有时也数据结构中元间的关系。(×)3. 顺序方式的优点是密度大、删除运算效率高。(×)4、程序设计题1、单链表的结点结构定义如下： struct LinkNodeLinkNode *next; int data;请根据述函数的功能写程序。void Insert(LinkNode *h,LinkNode *s)/h 指向链表的头结点（即使链表中没有元素，头结点也存在。）/链表中元素已经递增有序/函数功能为将结点 s到链表 h 中。后链表仍然保持

6、递增的顺序LinkNode *p,*q;/q 指向 p 的前驱q=h;p=h->next; while(p)if(p->data>s->data)/寻找到点位置，sq->next=s; s->next=p;return;elseq=p; (1 分)p=p->next; (1 分)/当表中没有比 s 大的结点时，s->next=q->next; (2 分)q->next=s; (2 分)到表尾第 3 章 栈和队列1、填空题1. 栈和队列在本质上都是线性表。2. 栈的操作特点是 后进先出_。队列的操作特点是_先进先出 。2、选择题1.消除

7、递归不一定需要使用栈，此说法A。A. 正确B. 错误2.用单循环链表表示队列，正确的说法是 B。(A)可设一个头指针使入队、出队都方便； (B)可设一个尾指针使入队、出队都方便；(C) 必须设头尾指针才能使入队、出队都方便；(D) 无论如何,只可能使入队方便。3、题1.栈的特点是先进先出。（ ×）2.可以在队列的任意位置元素。（ ×）3.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（）4.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（）第 4 章 串1、选择题1. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算

8、称作（ B）A连接B模式匹配C求子串D求串长2、题1.空串和空格串是同一个概念，二者没有区别。（ ×）第 5 章 数组和广义表1、填空题1.二维数组在内存中一种是 列优先可以有两种。方式，一种是行 优先，2.设广义表 L(（），（），（）)。则 head(L)是（）；tail(L)是(（），（）) ；L 的长度是3；L 的深度是3。3.设广义表 L(（a），（b），（c）)则 head(L)是 （a） ；tail(L)是 (（b），（c）)_。2、选择题1.在 C 语言中，如果有数组定义 intA89；假定每个整型数据占 2字节，则数组元素 A44的地址是（ A）。A. A+80B.

9、 A+76C.A+82D.以上都不对2.广义表 A=（a,b,(c,d),(e,(f,g)）,则下面式子的值为(D Head(Tail(Head(Tail(Tail(A)；A（g）B.(d)C.cD.d3、题1.在 C 语言中，数组的采取的是行优先的方式。（ ）2.广义表在本质上也是线性表。（×）3.可以用三元组法来压缩稀疏矩阵。（ ）4. 已知广义表 A=(a,b,c),(d,e,f), 从A 中取出原子 e 的运算是)head(tail(head(tail(A)。(第 6 章 树和二叉树1、填空题1. 一 棵62个 叶 结 点 的 完全 二 叉 树 , 最 多 有 (1+2+32

10、)+(62-1)=124个结点。2.若规定仅有根的二叉树的高度为 1，那么高为 h 的完全二叉树最多有- 2h-1个结点，最少有2(h-1)个结点。3. 设只包含有根结点的二叉树的高度为 0，则高度为 k 的二叉树的最大结点数为2(k+1)-1，最小结点数为k+1。4. 设仅包含根结点的二叉树的高度为 1，则高度为 k 的二叉树的最大结点数为2k-1，最小结点数为k。2、选择题1.具有 N 个结点的完全二叉树的深度是 B。(A) log2N(B) log2N +1(C) log2(2N)(D) log2N -12.设二叉树的树根为第一层，则第 i 层上至多有C结点。(C)2i-1(A)1(B)

11、2(D)2i-13、题1.二叉树的左右子树次序是严格的，不能够任意改变。（ ）2. 若根为第一层， 则深度为 k 的满二叉树的结点为 2k-1 。（ ）3.二叉树的三叉链表结构可以方便的到双亲结点。（ ）4、应用题1.在一段文字中，共出现 a、b、c、d、e、f 六种字符，每种字符出现的频率分别为 7,9,12,22,23,27。请回答下列问题：（1） 什么是哈夫曼树？（3 分）（2） 根据题目所给频率值，画出相应的哈夫曼树。（11 分）（3） 给出各个字符对应的哈夫曼编码。（6 分）（4） 该段文过哈夫曼编码后，长度是多少。（4 分）参考（1）如下：为：带权路径长度最小的二叉树称为哈夫曼树。

12、（3 分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11 分，每个结点 1 分）01100550145012223272801edf121601c79ab（3）给出各个字符对应的哈夫曼编码。（6 分）a:1110b:1111c:110d:00e:01f:10（4）该段文过哈夫曼编码后，长度是多少。（4 分）(7+9)*4+12*3+(22+23+27)*2=244或者 100+45+55+28+16=2442. 设一棵二叉树的先序遍历序列为 abcde，中序遍历序列为 badce，请画出对应的二叉树，并写出对应后序遍历序列。（15 分）参考如下：(1)画出二叉树（10 分）错一个结点扣

13、2 分。abcde（2）后序遍历序列为：bdeca（5 分）3. 通信报文中出现的字符 A、B、C、D、E，在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共 14 分）参考如下：为处理方便，关键字都乘以 100，为23，20，32，12，13构造哈夫曼树为：（9 分,每个结点 1 分）100014357010132202325CAB011213DE所以编码为：A：01编码 1 分）B：00C：11 D：100E：101（5 分，每个4.请证明对于任何一棵二叉树，如果其终端结点数为 n0，度

14、为 2 的结点数为 n2，则 n0=n2+1。（10 分）证明：令树中结点总数为 N，度为 1 的结点个数为 n1。则树中结点数满足下列公式：n0+n1+n2=N从度的角度来考虑，满足下列公式：2n2+n1+1=N 从而得证：n0=n2+15.请按照孩子-兄弟表示法，将图 1 所示树转化为二叉树。（共 14 分）ACBDEFG图 1解：ABCDEFG（每个结点 2 分）6.已知某二叉树的前序遍历序列为：A A F G。请画出该二叉树。如下：B CD E F G 和中序遍历序列为：C B E DABFCDG7. 已知通信联络中只可能出现 A、B、C、D、E、F、G、H 共 8 种字符，其出现次数

15、分别为 5，28，7，9，14，23，3，11 次。（1） 请画出赫夫曼树（权值小的结点在左边）。（15 分）（2） 计算该树的带权路径长度。（3 分）：（1）赫夫曼树构造如下。树中结点位置正确者，每个 1 分，共15 分。2330（2）该树的带权路径长度为（5+3+7+9）*4+（11+14）*3+（23+28）*2=2733 分5、读程序写结果已知二叉树的结点结构如下：struct Nodeint data;Node *lchild,*rchild;某棵二叉树的形态如右图：ABCDE根据要求解答下题：1、 (共 5 分)int fun1(Node *root)if(root=0) retu

16、rn 0; int l,r;l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r) return l+1; else return r+1;（1） 当 root 是指向结点 A 的指针时，函数 fun1 的返回值是多少？(2 分)函数 fun1 的返回值是 3。（2） 函数 fun1 的功能是什么？(3 分) 函数 fun1 的功能是求二叉树的高度。2、 (共 6 分)int fun2(Node *root)if(root=0) return 0;int l=fun2(root->lchild ); int r=fun2

17、(root->rchild ); return l+r+1;（1） 当 root 是指向结点 A 的指针时，函数 fun1 的返回值是多少？(2 分)函数 fun1 的返回值是 5。（2） 函数 fun1 的功能是什么？(4 分)函数 fun1 的功能是求二叉树中所有结点的个数第 7 章 图1、填空题1. 有 n 个顶点的有向连通图最多有 n(n-1) 条边，最少有 n条边。2. 具有 n 个顶点的完全无向图有n(n-1)/2 条边，完全有向图有 n(n-1)条边。2、选择题1.B方法可以出一个有向图中是否有环（回路）。(A)深度优先遍历 (B)拓扑排序(C)求最短路径(D)求关键路径2

18、.关键路径是指B。(A)从开始到终止路径长度最短的路径(B)从开始到终止路径长度最长的路径(C)从开始到终止活动最少的路径(D)从开始到终止活动最多的路径3、题1.具有 n 个顶点的有向图最多有 n*(n-1)条边。（ ）2.在 AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以为先决条件。（ ）4、应用题1、已知某图的列。(11 分)结构如下，试写出该图从顶点 A 开始的深度优先遍历序ABCDEFGHIJKABCDEFGHIJK为：ABGCHDIEJFK(对一个 1 分)2. 请给出图 1 的所有最小生成树。（10 分）26ab35ef1cd68图 1011111000000000

19、0010000000000010000000000010000000000010000000000010100000000000100000000000100000000000100000000000100000共两棵。第一棵为：(5 分)错一条边扣 1 分。2ab35ef1cd6第二棵为：(5 分)错一条边扣 1 分。26ab35ef1cd63. 已知某图采取如图 2 所示的邻接矩阵表示法，请回答下列问题。（共 12分）0123456123456123456011000100110100011010000011000001000ABCDEF图 2(1) 请画出该图。（6 分）（2）对其从顶点

20、 A 开始进行深度优先遍历，写出遍历序列。（6 分）（1） 请画出该图。（6 分）错一个结点扣 1 分。ABCDEF（2）对其从顶点 A 开始进行深度优先遍历，写出遍历序列。（6 分, 个字符扣 1 分）序列为：ABDECF错一4、（本题总计 7 分）构造该图的最小生成树。 2gbe222211ad314cfh1图的最小生成树如下每条边 1 分，共 7 分beg22211ad1cfh1第 9 章 查找1、选择题1.若性表中采用二分查找法查找元素，该线性表应该(C)。A元素按值有序B采用顺序结构C元素按值有序，且采用顺序D元素按值有序，且采用链式结构结构2.对二叉排序树进行B遍历，可以得到该二叉

21、树所有结点序序列。的有(A) 前序(B)中序(C)后序(D)按层次3.利用逐点法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素 34 要进行(A )元素间的比较。A4 次B5 次C. 7 次D104.对二叉排序树进行遍历，可以得到该二叉树所有结点的有序序列。(A) 前序(B)中序(C)后序(D)按层次5.散列函数有一个共同性质，即函数值应按(C )取其值域的每一个值。D.平均概率A.最大概率B.最小概率C.同等概率6.一个哈希函数被认为是“好的”，如果它满足条件 A 。 (A)哈希地址分布均匀(B) 保证不产生(C) 所有哈希地址在表长范围

22、内(D)满足(B)和(C)7.哈希表的平均查找长度是D的函数。（A）哈希表的长度（C）哈希函数（B）表中元素的多少（D）哈希表的装满程度8.平均查找长度最短的查找方法是C。（A）折半查找（B）顺序查找 （C）哈希查找 （4）其他2、题1.在有序表的过程中，设立“哨兵”的作用是为了提高效率。（）2.对于折半查找，其前提条件是待查找序列只要是有序的即可。（）3、应用题1.若一棵排序二叉树的关键字输入序列为80，6，10，7，8，25，100，90，请画出该二叉树。解：二叉排序树为： （16 分，每个结点 2 分）801006901072582.已知一组关键字为1,14,27,29,55,68,10,11,23，则按哈希函数 H(key)=keyMOD 13 和链地址法处理来构造哈希表。（1）画出所构造的哈希表。（2）在的查找概率相等的前提下，计算该表查找时的平均查找长度。（1）画出所构造的哈希表。9 个结点，每个 1 分0123456789101112（2）在的查找概率相等的前提下，该表查找时的平均 2 分查找长度，ASL（1×42×33×2）/9=16/94、程序设计题1.已知整型