《2022年数据结构试题 3.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题 3.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、模拟试题 4一、单项选择题1.下面程序段的时间复杂度是( )for(i=0;in;i+) for(j=1;jnext; B.p-next=p-next-next;C.p-next=p; D.p=p-next-next;3.在头指针为 head且表长大于 1的单循环链表中，指针p指向表中某个结点，若 p-next-next=head,则( )A.p指向头结点 B.p指向尾结点C.*p的直接后继是头结点 D.*P的直接后继是尾结点4.判定“ 带头结点的链队列为空” 的条件是 ( )A. Q.front=NULL B. Q.rear=NULLC. Q.front=Q.rear D. Q.front!
2、=Q.rear5.设有两个串 T和P，求 P在T中首次出现的位置的串运算称作( )A.联接 B.求子串 C.字符定位 D.子串定位6.广义表 A=(a,(b),(),(c,d,e) 的长度为 ( )A.4 B.5 C.6 D.77.一棵含 18个结点的二叉树的高度至少为( )A.3 B.4 C.5 D.68.已知二叉树的先序序列为ABDECF ，中序序列为 DBEAFC ，则后序序列为 ( )A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA9.无向图中一个顶点的度是指图中( )A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数C.通过该顶点的回路数 D.与该顶点连通的
3、顶点数10. 在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 A.05 B. 1 C. 2 D.4 11.在下列排序方法中，平均时间复杂度为O(nlogn)且空间性能最好的是( )A.快速排序 B.堆排序 C.归并排序 D.基数排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 12.已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并
4、的结果是( )A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,79,8213. 设有序表的关键字序列为 1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。A.2 B. 3 C. 4 D. 1214以下说法正确的是 （ ）A.查找表中数据元素的任何数据项都可以作为关键字。B.采用二分查找法对有序表进行查找总比采用顺
5、序查找法对其进行查找要快C.二叉排序数的查找和二分查找时间的性能相同。D.最佳二叉排序树一定是平衡二叉树15.倒排文件的主要优点是( )A.便于进行插入和删除运算 B.便于进行文件的恢复C.便于进行多关键字查询 D.节省存储空间二、填空题1.抽象数据类型的特点是将_和_封装在一起，从而现实信息隐藏。2.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需_一个位置。3.在队列中，允许进行插入操作的一端称为_，允许进行删除操作的一端称为 _。4.对于顺序栈而言，在栈满状态下，如果此时再做进栈运算，则会发生“_”。5.设S1=good,S2= ,S3=book ，则 S1，S2和S3依次联接
6、后的结果是_。6.假设三维数组 A1098 按行优先顺序存储，若每个元素占3个存储单元，且首地址为 100，则元素 A987 的存储地址是 _。7.已知在一棵含有 n个结点的树中，只有度为k的分支结点和度为 0的叶子结点，则该树中含有的叶子结点的数目为_。8.能够成功完全拓扑排序的图一定是一个_。9.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 序两者之中，选用 _较
7、为适当。10. 散列文件删除记录时，仅需对被删记录_即可。三、解答题1.假设通信电文使用的字符集为a,b,c,d,e,f ，名字符在电文中出现的频度分别为： 34，5，12，23，8，18，试为这 6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值 )，然后分别写出每个字符对应的编码。2.已知两个 45 的稀疏矩阵的三元组表分别如下：014160 1132122181 2222234252 2569342283 34254 4251请画出这两个稀疏矩阵之和的三元组表。3.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，3
8、2，构造一棵二叉排序树。(1)画出该二叉排序树(2)画出删去该树中元素值为90的结点之后的二叉排序树。四、算法设计题1.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7，10，10，21，30，42，42，42，51，70)经算法操作后变为(7，10，21，30，42，51，70)2稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。3假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“ ”和“ ”以及花括号与“ ”和“”，且这三种括号可按任意的次
9、序嵌套试用，如（. . . . . . . .( . . . .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -