《数据结构试题B1.docx》由会员分享，可在线阅读，更多相关《数据结构试题B1.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构试卷及答案 米 1 .算法分析的目的是(C)。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性. ( B )是具有相同特性数据元素的集合，是数据的子集。A.数据符号B.数据对象C.数据D.数据结构.用链表表示线性表的优点是(C )。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同.输入序列为(A,B,C,D)不可能的输出有(D )oA.(A,B,C,D)B. (D,C,B,A) C. (A,C,D,B) D, (C,A,B,D).在数组表示的循环队列中，front、rear分别
2、为队列的头、尾指针，maxSize为数 组的最大长度，队满的条件是(B )。A. front二maxSizeB. (rear+1 )%maxSize=frontC. rear=maxSizeD. rcar=front.设有串 l=I am a good sludenl那么 Subslr(l,6,6)= ( D )。A. studentB. a good s C. goodD. a good.设有一个对称矩阵A,采用压缩存储方式，以行序为主序存储all为第一个元素， 其存储地址为1,每个元素占一个地址空间，那么a85地址为(B )oA.23B.33C.18D. 40.广义表LS=(A,(B,C,
3、D),E)运用head和tail函数，取出LS中原子B的运算 (C )。B. Gettail(Gethead(LS)D. Gethead(Gettail(LS)A. Gethead(Gethead(LS)C. Gethead(Gethead(Gettail(LS).假设一棵二叉树先序序列为ABCDEFG,中序序列为CBDAEGF,那么其后序序 列为（A） oA. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE.以下存储形式中，（C ）不是树的存储形式。A.双亲表示法B.左子女右兄弟表示法C.广义表表示法D.顺序表示法.对待排序的元素序列进行划分，将其分为左、右两个子
4、序列，再对两个子序列 施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 （C）oA.直接选择排序B.直接插入排序C.快速排序D.起泡排序.采用折半查找方法进行查找，数据文件应为（A）,且限于（）oA.有序表顺序存储结构B.有序表链式存储结构C.随机表顺序存储结构D.随机表链式存储结构.就平均查找速度而言，以下几种查找速度从慢至快的关系是（B ）A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半.执行下面程序段时，执行S语句的次数为（D ）for(int 1=1 ;I=n;I+) 米 米 米 for(intj=l;j=I;j+)S；A. n2
5、B. n2/2 C. n(n+l) D. n(n+1 )/2.串是一种特殊的线性表，其特殊性表达在(B )A.可以顺序存储B.数据元素是一个字符C.可以钱接存储D.数据元素可以是多个字符.树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先 序遍历、中序遍历和后序遍历。结论(A)是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对.由五个分别带权值为9, 2, 3, 5, 14的叶子结点构成的一棵哈夫曼树，该树的 带权路径长度为(C)。A. 60
6、B. 66C. 67D. 50. 一棵二叉树有67个结点，这些结点的度要么是0,要么是2。这棵二叉树中度 为2的结点有(A)个A. 33B. 34C. 32D. 30.有一个有序表为1,3912,32,41,45,62,75,77,82,95,100),当二分查找值82为的结点 时，(C)次比拟后查找成功。A. 1 B. 2C. 4D. 8.假设有文件的关键字序列为：265H301H751 129 937 863 742 694 076438,以下为二路归并排序过程。第二趟为:DAJ265 301 129 751 863 937 694 742 076 438B.076 129 265 301
7、 438 694 742 751 863 937C.I29 265 301 694 742 751 863 937 076 438D.129 265 301 751 694 742 863 937 076 438二、填空题(本大题共6小题，每空2分，共12分；答案填在下表内)1算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法 还具有五个重要特性，它们分别是有穷性 确定性可行性有零或多个输入和有一或多个输出。2算法优劣的五个标准是正确性、可使用性、-可读性 健壮性 效率.3有n个球队参加的足球联赛按主客场制进行比赛，共需进行血山场比赛。4设 有串 t=I am a stud
8、ent s-good,那么 Concat(t,s)= I am a student good, Substr(t.87)= student15 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲 区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。 该缓冲区应该是一个队列结构,其主要特点是先进先出。6广义表(a),a)的表头是3_,表尾是皿。三、判断题(对的打“ J”，错的打“X”。每题1分，共10分;答案填在下表内) TI数据的逻辑结构与数据元素本身的内容和形式无关。F2三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。T3中序序列和后序序列相同的
9、二叉树为：空树和缺右子树的单支树。T4对于两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历后得到的 关键字排列顺序相同。F5 序列30, 40, 50, 15, 25, 35, 38, 10是堆。 派订 F6对于无向图的生成树，从同一顶点出发所得的生成树相同。T7假设设哈希表长m=14,哈希函数H(key)=key%ll,表中已有4个结点。 addr( 15)=4 addr(38)=5 addr(6l)=6 addr(84)=7 其余地址为空，如用二次探测再散 列处理冲突，关键字为49的结点的地址是9。T8 一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右) 用自然数依
10、此对结点编号那么，那么编号最小的叶子的序号是2皿+1 ；编号是i的结 点所在的层次号是1。故+1。(Uogi|表示向上取整(根所在的层次号规定为 I层)。F9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。T10算法可以没有输入，但是必须有输出,四、画出树的孩子兄弟表示法示意的树或森林。(4分)五、要求题（本大题共2小题，共12分）设关键字的输入序列为4, 5, 7, 2, 1, 3, 6.（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态, 假设发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。1 . （4分）上面的数据作为待排序的数据，写出用快速排序进行一趟
11、划分后的 数据序列六、按要求做题（本大题共2小题，共12分） 派订 2用prim算法求以下图的最小生成树，写出最小生成树的生成过程。（5分） 1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优七、算法分析设计题(本大题共5小题，共30分)1.写出程序段的功能，并给出一个测试用例(一个输入数据和一个输出结果) (5 分)。void conversion()(Stack s;int n;SElemType e;initstack(s);printf(Please input number:*);scanf( %d，&n);while(n)push(s, n%8);n=n/8;w
12、hile(!stackempty (s)pop(s, e);printf( data);if(p-rchild!=NULL) (3) ; stacktop=p-rchiId;)if( (4) ) top+; (5) ;(4)(1) T(4)top0top+p-lchild!=NULL(5) stacktop=p-lchiId3.请在标号处填写合适的语句。完成以下程序。(每空1分，共5分)int Binary_Search(S_TBL tbl, KEY kx) 在表Ibl中查找关键码为kx的数据元素，假设找到返回该元素在表中的位置，否那么, 返回0 */int mid, flag=()；low=
13、 1 ； high=lenglh；while( (1) &!flag_)/*非空，进行比拟测试*/mid=_ (2)；if(kxtbLelemmid.key) (4)；else flag= (5)； break ： ) return flag;)(1)(2)(3)(4)(5)Iow=high(low+high)/2high=mid-l(1) low=mid+l14.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。（每空1分，共5分） 派订 米 程序：Void seletesort(int An, int n) (int i, j,t, minval, minidx;for(i=l;i=n-l;i+)(minval=Ai+l;(1)for(j=i+2;jAjminval=Aj(1) i!=jAi+l=Aminidx5试写出求有向无环图的关键路径算法的设计思路（10分）输入顶点和瓠信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的VI i计算每条瓠的ei和li,找出= 的关键活动