山东交通学院成人高考数据结构复习题及参考答案

《数据结构》（A）复习题一、选择题（每小题2分，共30分）1.计算机算法必须具备输入.输出.（B）等5个特性。A.可行性.可移植性和可扩展性B.可行性.确定性和有穷性C.确定性.有穷性和稳定性D.易读性.安全性和稳定性2.树形结构是数据元素之间存在一种（D）。A.一对一关系 B.多对多关系C.多对一关系 D.一对多关系3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（C）。A.O(log2n) B.O(1) C.O(n) D.O(n2)4.链表不具有的特点是（A）。A.可随机访问任一元素 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比5.栈的操作特点是（C）。A.随机存取 B.顺序存取 C.先进后出D.先进先出6.队列的删除操作是在（B）。A.队尾 B.队头 C.队列任意位置 D.队头元素后7.下列表示方法中，（A）不常用来存储稀疏矩阵。A.索引表 B.三元组 C.带行指针向量的链接存储 D.十字链表8.广义表C=(a,(b,c,d))的长度是（A）。A.2 B.3 C.4 D.59.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（C）个。A.-1B.0C.1D.210.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C）。A.1/2倍 B.1倍 C.2倍 D.3倍二、综合分析题（每题8分，共40分）1.已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H,A,C,K,I,L,F。画出这棵二叉树。（8分）答案：A/\BC/\\DEF\\/GHI//\JKL2、设某密码电文由8个字母组成，每个字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。（8分）答案：100/\4060/\/\19212832/\1117/\/\56710/\238个字母的编码分别为：19（00）、21（01）、2（10000）、3（10001）、6（1001）、7（1010）、10（1011）、32（11）3、3.画图给出序列（45,36,18,53,72,30,48,93,15,36），构建堆的过程。（8分）4、4.已知图G的邻接矩阵如下所示：1）求从顶点1出发的广度优先搜索序列；2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程（用图的方式表示即可）。（8分）答案：(1)广度优先遍历序列：1;2,3,4;5;(2)最小生成树（prim算法）5、5.假定n=8，数组A中8个元素的排序码为(36，25，48，12，65，43，20，58)，采用直接选择排序，试给出其排序过程。（8分）答案：0)[3625481265432058]1)12[25483665432058]2)1220[483665432558]3)122025[3665434858]4)12202536[65434858]5)1220253643[654858]6)122025364348[6558]7)1220253643485865算法设计题（共30分）1.从顺序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。（15分）答：从顺序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。类型定义：structList{ ElemTypelist[MaxSize]; intsize;//当前线性表长度};算法：voidDelete3(List&L,ElemTypes,ElemTypet)//从线性表中删除其值在给定值s和t之间的所有元素{inti=0;while(i<L.size)if((L.list[i]>=s)&&(L.list[i]<=t)){for(intj=i+1;j<L.size;j++)L.list[j-i]=L.list[j];L.size--;}elsei++;}2、编写递归算法，计算二叉树的深度。答案：二叉树链接存储结构的结点类型可定义为StructBTreeNode{ElemTypedata;BTreeNode*left;BTreeNode*right;};其递归算法如下：intDepthBTree(BTreeNode*BT)//求由BT指针指向的一棵二叉树的深度{if(BT==NULL)return0;//对于空树,返回0并结束递归else{//计算左子树的深度intdep1=BTreeDepth(BT->left);//计算右子树的深度intdep2=BTreeDepth(BT->right);//返回树的深度if(dep1>dep2)returndep1+1;elsereturndep2+1;}}《数据结构》B复习题一、选择题（每小题2分，共30分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（B）和运算的学科。A.结构B.关系C.运算D.算法2.为了描述n个人之间的同学关系，可用（C）结构表示。A.线性表B.树C.图D.队列3.在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（B）个元素。A.n-i B.n-i+1 C.n-i-1 D.i4.从表中任一结点出发，都能扫描整个表的是（C）。A.单链表 B.顺序表 C.循环链表 D.静态链表5.队列的操作特点是（D）。A.随机存取 B.顺序存取 C.先进后出 D.先进先出6.一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（C）。A.a,b,c,d,eB.d,e,c,b,a C.d,c,e,a,bD.e,d,c,b,a7.对稀疏矩阵进行压缩存储目的是（C）。A.便于进行矩阵运算 B.便于输入和输出C.节省存储空间 D.降低运算的时间复杂度8.广义表C=((),(d),(a,(b,c)))的长度是（B）。A.2 B.3 C.4 D.59.（A）的遍历需要先访问根节点，再访问左子树，最后访问右子树。A.前序遍历B.中序遍历C.后序遍历D.层次遍历10.在一个图中，所有顶点的度数之和等于所有边数的（C）倍。A.1/2B.1C.2 D.4综合分析题（每题8分，共40分）1、A/\A/\BC/\\DEF\\/GHI//\JKL图1答案：括号表示法：A(B(D(,G(J)),E(,H)),C(,F(I(K,L))))（3分）前序：ABDGJEHCFIKL（1分）中序：DJGBEHACKLIF（1分）后序：JGDHEBKLIFCA（1分）2.由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，求该树的带权路径长度。23/\23/\914/\77/\25带权路径长度：9*1+7*2+7*2+2*3+5*3=44.3、3.已知图如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）答案4、4.假定8个元素的排序码为(36,25,48,12,65,43,20,58)，采用气泡排序，试给出其排序过程。0)[3625481265432058]1)12[36254820654358]2)1220[362548436558]3)122025[3643485865]4)12202536[43485865]5)1220253643[485865]6)122025364348[5865]7)1220253643485865]5、一个散列存储的数据集合B=(18,75,60,43,54,90,46,31,58,73,15,34)，散列空间大小为m=13，采用除留余数法。答案：（散列表5分）查找成功时平均查找长度为：ASL=(8×1＋3×2+1×3)/12=17/12（3分）三、算法设计题（共30分）（编写算法前，请给出使用数据结构的类型定义）1.从线性表中删除第i个元素并由函数返回。1、类型定义：structList{ ElemTypelist[MaxSize]; intsize;//当前线性表长度};算法：、intDeletel(List&L,inti){if(i<1||i>L.size){cerr<<"Indexisoutrange!"<<end1;exit(1);}ElemTypex;x=L.list[i-1];for(intj=i-1;j<L.size-1;j++)L.li