《数据结构试题B2.docx》由会员分享，可在线阅读，更多相关《数据结构试题B2.docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、A、front- next=s；front=s；B、s- next=rear；rear二s；C、rear- next=s；rear=s；D、s- next=front；front=s；第2学期数据结构试卷A 米 米 一、 选择题(本大题共15小题，每题2分，共30分；答案填在下表内).从一个长度为100的顺序表中删除第3()个元素时需向前移动 A 个元素A、70 B、71 C、69I)、30.在一个具有N个单元的顺序表中，假定以地址低端(即下标为1的单元)作为底，以 top作为顶指针，那么当做进栈处理时top变化为_D。A、 top 不变 B、top=0 C、top=top-l D, top=
2、top+l.从一个具有n个结点的单链表中查找其值等于x结点时一，在查找成功情况下，那么平 均比拟D_个结点。A、 n B、 n/2 C、 (n-l)/2 D、 (n+l)/2.在一个单链表中，假设要删除p指针所指结点的后继结点，那么执行BA、 p- next； p- next=p- next- next；B、 p- next=p- next- next；C、 p=p- next；D、p=p- next-next；.在一个链队列中，假定front和rear分别为队首和队后指针，那么进行插入S结点的 操作时应执行C_o.在一棵度为3的树中度为3的结点数为3个，度为2的结点数为1个，度为1的结 点数
3、为1个，那么度为0的结点数为/一个A、 6 B、 7 C、 8 D、 9.假定一棵二叉树的结点数为33个，那么它的最小高度为最大高度为_C_A、 4,33 B、 5,33 C、 6,33 D、 6,32.在一棵完全二叉树中，假设编号为i的结点有右孩子，那么该结点的右孩子编号为 _B_oA、 2i B、 2i+l C、 2i-l D、 i/2.在一个有向图中，所有顶点的入度之和等于所有弧数和_A_倍。A, 1 B、2 C、3 D、4.对于一个具有N个顶点的图，假设用邻接矩阵表示，那么该矩阵的大小为_D_。A、 N B、 (N-l)2 C、 (N+l)2 D、 N2.一个图如下图，在该图的最小生成
4、树中各边上数值之和为_B_o1 .一个图如下图，由该图行到的一种拓朴序列为A、 vl v4 v6 v2 v5 v3 米 B、 vlv2v3v4v5v6C、 vlv4v2v3v6v5D、 vlv2v4v6v3v5.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从（）到4,列下标j的范围从。到5, M按行存储时元素M2 4的起始地址 与M按列存储时元素D的起始地址相同。A、m2 4 B、M4 2 C、M3l D, M3l.具有6个结点的无向图至少应有 A条边才能保证是连通图。A、5 B、6 C、 7 D、 8.采用邻接表存储的图的深度优先遍历类似于二叉树的。A先序遍
5、历B中序遍历C.后序遍历D.按层遍历二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内）12345678.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结 构表示，根据数据元素之间关系的不同特性，通常有以下四类基本结构：集合、线 性结构、 和 （2）。1 .评价算法的标准很多，通常是以执行算法所需要的 （3）和所占用的（4）来 判别一个算法的优劣。2 .线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的位置也是相 邻的。3 .空格串的长度为串中所包含二豆字符的个数，空串的长度为3.加上表示指向前驱和的线索的二叉数称为线索二叉树。三、判断题（对的打“J”，
6、错的打“X”。每题1分，共10分）（X ） 1.线性表的唯一存储形式是链表。（）2.指针P指向键表L中的某结点，执行语句p=p-next不会删除该链表 中的结点。（）3.在链队列中，即使不设置尾指针也能进行入队操作。（X ） 4.如果一个串中的所有字符均在另一串中出现，那么说前者是后者的子串。（X） 5.设与一棵树T所对应的二叉树为BT,那么与T中的叶子结点所对应的BT中 的结点也一定是叶子结点。（）6.快速排序是不稳定排序。（Y） 7.任一 A0E网中至少有一条关键路径，且是从源点到汇点的路径中最短的一 条。（Z） 8.假设图G的最小生成树不唯一，那么G的边数一定多于1,并且权值最小的 边有
7、多条（其中n为G的顶点数）。（AA） 9.绐出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（X） 10.基数排序是多关键字排序。从最低位关键字起进行排序。四、应用题。（共44分）.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分） .假设用于通信的电子由字符集匕,2。,56,。85中的字母构成，这8个字母在电 文中出现的概率分别为0.07, 0. 19, 0. 02, 0. 06, 0.32, 0. 03, 0.21, 0.10画出 哈夫曼树，并为这8个字母设计哈夫曼编码。（8分）.序列70, 73, 69, 23, 93, 18,11, 68请给出直接
8、插入排序作升序排序每 一越的结果和快速排序作升序排序时一越的结果。（10分） 派订 1 .设有一组关键字关键码集为47, 7, 29, 11, 16, 92, 22, 8, 3）,哈希表表长 为11, Hash （key） =key mod 11,用线性探测法处理冲突，构造哈希表，并求它成功 查找的ASL。（8分）米 米 米 2 .二叉树的先序遍历序列为ABCDEFGHI,中序遍历序列为B C A E D GH F I,画出这棵二叉树。（6分）五、算法设计题（8分）定义有序表抽象数据类型，并据此类型设计折半查找算法。typedef struct int key；float info；）JD；int binsrch（JD r,int n,int k） int low,high,mid,found；1ow=1； high=n； found=0；wh i1e (1owrmid, key) low=mid+l；else if(k=rmid. key) found=l；else high=mid-l；)if(found=l)return(mid)；elsereturn (0)；)