数据结构习题集和答案

第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.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4.下面关于算法说法错误的是（D）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的3、应用题1、给出以下算法的时间复杂度.voidfun(intn){inti=1,k=100;while(in){k=k+1;i=i+2;}}时间复杂度为____O（n）_____。2、给出以下算法的时间复杂度.voidfun2(intn){inti=1,k=100;while(in){i=i*10;k=k+1;}}时间复杂度为____O（logn）___________。第2章线性表1、填空题1.线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。2.顺序表采用__随机___访问机制对数据元素进行访问。3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为:①____s-next=p-next_____________；②____p-next=s___________________；4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。2、选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。(A)n(B)2n－1(C)2n(D)n-12.在单链表中，如果在结点p之后插入一个新结点s，其操作为A。（A）s-next=p-next;p-next=s;（B）p-next=s;s-next=p-next;（C）s-next=p;p-next=s-next;（D）p-next=s;s-next=p;3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(C)。(1≤i≤n)A．O(0)B．O(1)C.O(n)D．O(n2)4.若长度为n的线性表采用顺序存储结构，在其第i个位置前插入一个新元素需要移动的元素个数为(B)。(1≤i≤n+1)A．n-iB．n-i+1C.iD．n-i-13、判断题1.线性表中每一个元素都有一个前驱和一个后继。（×）2.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)3.顺序存储方式的优点是存储密度大，插入、删除运算效率高。(×)4、程序设计题1、单链表的结点结构定义如下：structLinkNode{LinkNode*next;intdata;};请根据述函数的功能写程序。voidInsert(LinkNode*h,LinkNode*s){//h指向链表的头结点（即使链表中没有元素，头结点也存在。）//链表中元素已经递增有序//函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序LinkNode*p,*q;//q指向p的前驱q=h;p=h-next;while(p){if(p-datas-data){//寻找到插入点位置，插入sq-next=s;s-next=p;return;}else{q=p;(1分)p=p-next;(1分)}}//当表中没有比s大的结点时，插入到表尾s-next=q-next;(2分)q-next=s;(2分)}第3章栈和队列1、填空题1.栈和队列在本质上都是___线性表__________。2.栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。2、选择题1.消除递归不一定需要使用栈，此说法___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中首次出现的位置的运算称作（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语言中，如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（A）。A.A+80B.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)+(62-1)=124______个结点。2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有-____2^h-1___________个结点，最少有___2^(h-1)______个结点。3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为____2^(k+1)-1____________，最小结点数为____k+1____________。4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为_______2^k-1_________，最小结点数为____k______。2、选择题1.具有N个结点的完全二叉树的深度是__B______。(A)log2N(B)log2N+1(C)log2(2N)(D)log2N-12.设二叉树的树根为第一层，则第i层上至多有__C_____结点。(A)1(B)2(C)2i-1(D)2i-13、判断题1.二叉树的左右子树次序是严格的，不能够任意改变。（√）2.若根为第一层，则深度为k的满二叉树的结点为2^k-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）答案为：带权路径长度最小的二叉树称为哈夫曼树。（3分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11分，每个结点1分）（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分）错一个结点扣2分。fc287912222355162745100abed1000001111（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分）所以编码为：A：01B：00C：11D：100E：101（5分，每个编码1分）4.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（10分）ABDEC010001111004357202325321213abcde证明：令树中结点总数为N，度为1的结点个数为n1。则树中结点数满足下列公式：n0+n1+n2=N从度的角度来考虑，满足下列公式：2n2+n1+1=N从而得证：n0=n2+15.请按照孩子-兄弟表示法，将图1所示树转化为二叉树。（共14分）解：（每个结点2分）6.已知某二叉树的前序遍历序列为：ABCDEFG和中序遍历序列为：CBEDAFG。请画出该二叉树。答案如下：ACBDEFG图1ACBDEFGBCDFGA7.已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符，其出现次数分别为5，28，7，9，14，23，3，11次。（1）请画出赫夫曼树（权值小的结点在左边）。（15分）（2）计算该树的带权路径长度。（3分）答案：（1）赫夫曼树构造如下。树中结点位置正确者，每个1分，共15分。（2）该树的带权路径长度为（5+3+7+9）*4+（11+14）*3+（23+28）*2=273————3分301416791004223191183558285、读程序写结果已知二叉树的结点结构如下：structNode{intdata;Node*lchild,*rchild;};某棵二叉树的形态如右图：根据要求解答下题：1、(共5分)intfun1(Node*root){if(root==0)return0;intl,r;l=fun1(root-lchild);r=fun1(root-rchild);if(l=r)returnl+1;elsereturnr+1;}（1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分)函数fun1的返回值是3。（2）函数fun1的功能是什么？(3分)函数fun1的功能是求二叉树的高度。2、(共6分)intfun2(Node*root){if(root==0)return0;intl=fun2(root-lchild);intr=fun2(root-rchild);returnl+r+1;}ABCDE（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_