2022年数据结构试题整理 .pdf

《2022年数据结构试题整理 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题整理 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、一、单项选择题 (每小题 2 分, 共 30 分)在每小题的四个备选答案中选出一个正确答案 , 并将其代码写在题干后面的括号内。不选、错选或者多选，该题无分。1下列说法那种是不正确的（） 。 A 栈是一种受限制的线性结构 B 栈是一种后进现出的线性结构 C 栈可以是线性结构也可以是非线性结构 D 栈可以用数组或链表来实现2深度为 K 的二叉树，所含叶子的个数最多为（） 。 A 2K BK C2(K-1) D2K+1 3一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（） 。 A. 较快 B. 较慢 C. 相同 D. 不一定4判定线索二叉树中

2、某结点有左孩子的条件是 ( ) 。 A p!=NULL Bp-lchild!=NULL C p-ltag= =0 Dp-ltag= =1 5 若用数组 Sn 作为两个栈 S1和 S2的共用存储结构 , 对任何一个栈只有当Sn满时才不能用作入栈操作, 作这两个栈分配空间的最佳方案是( ) A S1的栈底位置为 0,S2 的栈底位置为 n B S1的栈底位置为 0,S2 的栈底位置为 n/2 C S1的栈底位置为 1,S2 的栈底位置为 n D S1的栈底位置为 1,S2 的栈底位置为 n/26对于一个具有n 个顶点的无向图 , 若采用邻接矩阵表示, 则该矩阵的大小是( )。 A n B2(n-1

3、) Cn-1 D2n 7在具有 n 个结点的单链表做插入、删除运算, 平均时间复杂度是 ( )。 A O(1) BO(n) CO(log2n) DO(n2 ) 8非空的循环单链表head的尾结点 ( 由指针 p 所指) 满足 ( )。 A p-next=NULL Bp=NULL C p-next=head Dp=head 9若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除一个元素, 则采用 ( )存储方式最节省运算时间。 A 单链表 B双循环链表 C 单循环链表 D容量足够大的顺序表10对于任何一棵二叉树T, 如果其终端结点数为n0, 度为 2 的结点数为 n2，则（） 。An0

4、=n2+ Bn2=n0+1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - Cn0=2n2+1 Dn2=2n0+1 11某二叉树的后根遍历序列为dabec, 中序遍历序列为 bebac, 则前序遍历序列为( )。 A acbed Bdecab Cdeabc Dcedba 12下列排序算法中，（）算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。 A 插入排序 B冒泡排序 C 堆排序 D 快速排序13. 用

5、某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（） 。A.选择排序 B.希尔排序 C.归并排序 D.快速排序14. 适于对动态查找表进行高效率查找的组织结构是（） 。A有序表 B分块有序表 C 三叉排序树 D 线性链表15. 如果只想得到1024 个元素组成的序列中的前5 个最小元素，那么用 ( )方法最快。A.起泡排序 B.快速排序 C.堆排序

6、D.直接选择排序二、填空题（每空1分，共 20分）1. 在按关键字递增的数组A12 中, 按二分查找方法进行查找时, 查找长度为3的元素个数为 _。2. 评价数据结构的两条基本标准是：和。3. 算法的五个特性是指、和。4. 已知一个图用邻接矩阵表示, 计算第 i 个结点的入度的方法是_。5. 循环队列用数组Am存放起元素值 , 已知其头尾指针分别是front和 rear,则当前队列中元素的个数是_。6. 通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。7. 一颗有 6 个结点的完全二叉树，其结点按编号存放数据为：A、B、C 、D、E、

7、F，若按中根遍历该树得到的数据序列为：。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 8. n个顶点的无向完全图具有条边， n 个顶点的有向完全图具有条弧。9. 在单链表上难以实现的排序方法有、。10. 在有序表（ 12，24，36，48，60，72，84）中二分查找关键字72 时所需进行的关键字比较次数为。11. 已知一颗完全二叉树中共有767 结点，则该树中共有个叶子结点。12.200 个结点的完全二叉树，其深度h= 。

8、三、简答题（共35分）1、下列程序的功能是什么？（5 分）Node * Demo (LinkList L, node *p) /*L 是带有头结点的单链表 q=L ; while (q!=NULL)&(q-next!=p) q=q-next ; if (q!=NULL) return q ; else error (“ *p not in L” ) ; 2、 给定一棵二叉树的两种遍历序列，分别是：中序： C B E D A F I G H 后序： C E D B I F H G A 1.构造出该二叉树（ 5分）2.画出该二叉树的后序线索化（5分）3、已知连通图的邻接矩阵如下: 0 1 12 5

9、 10 1 0 6 9 0 12 6 0 0 2 5 9 0 0 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 10 0 2 4 0 试画出连通图，并按 kruskal算法求其最小生成树， 按生成次序写出各条边。（10分）4、 对于给定的 8 个实数 W 8,6 ，23,15,4 ，20，35,10 ；试构造 huffman 树，并求出每个叶子结点的哈夫曼编码。 （10 分）四、程序算法（共15 分）对任意输入的一个非负

10、十进制整数，打印输出其二进制数，要求写出算法以及栈的结构定义（顺序，链式都可以） 。一、选择（共 30 分）1C 2 A 3 B 4 C 5 C 6B 7 B 8 C 9 D 10 A 11D 12 A 13 D 14 C 15 D 二、填空（每空 1 分，共 20 分）1. 4 2. 存储需要量和运算的时间效3. 有穷性 、确定性、可行性 、输入 和输出4. 计算第 i 列非零元素之和5. Rear-（front+m ）%m 6. 栈7. DBEAFC 8.1/2*n*(n-1) n*(n-1) 9. 快速排序、堆排序 、希尔排序10. 2 11. 384 12. h= 8 三、应用（ 35

11、分）1、 答: 功能是在带有头结点的单链表中找p 所指向的直接前驱。（5 分）2、A B G 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - Null 图 5 分先序序列 ABCDEGFIH (2 分) 线索化 3 分3、 9 5 1 最小生成树 1-2 3-5 4 6 4-5 1-4 10 12 （5 分） 2 图 5 分4、画出树 5 分，写成字符编码 3 分，求出 wpl 值 2 分。23：00 8：1100 4：010

12、0 10：1101 6：0101 20：111 15：011 35：10 Wpl=23*2+4*4+6*4+35*2+8*4+10*4+20*3=2884 6 10 8 18 20 38 35 73 48 23 25 10 15 4 1 2 3 5 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 四、算法程序typedef struct selemtype *base; Selemtype *top; sqstack; 写

13、出结构定义给 5 分Void conversion() initstack(S); Scanf(“ %d ” ，N); While (N) push(S,N % 2); N=N/2; While(! StackEmty(S) pop( S,e ); Printf(“ %d ” ,e); 算法给 10 分一、单项选择题 (每小题 2 分, 共 30 分)在每小题的四个备选答案中选出一个正确答案 , 并将其代码写在题干后面的括号内。不选、错选或者多选，该题无分。1设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作( )。 A连接 B模式匹配C求子串 D求串长2线性表的链式存储结构是

14、一种( )的存储结构。A随机存取 B顺序存取 C索引存取 D散列存取3循环队列 SQ采用数组空间 SQ.base0，n-1 存放其元素值，已知其头尾指针分别是 front和 rear ，则判定此循环队列Q为满队列的条件是 ( )。AQ front=Q rear BQ front!=Q rear CQ front=(Q rear+1) n DQ front!=(Qrear+1) n 4对有序表 1，3，9，12，32，41，45，62，75，77，82，95，100，当折半名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

15、理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 查找值为 82 的结点时 ( )次比较后查找成功。 A1 B2 C4 D8 5若串 s1=ABCDEFG ，S2=9898 ，S3=# ，S4=012345 ，函数 Concat(x,y)返回 x 和 y 串的连接串， Substr(s,i,j)返回串 s 从序号 i 开始的 j 个字符组成的子串，length(s)返回串 s 的长度，index(s,t,pos)返回子串在主串中的位置，replace(s,t,v) 为用 v 替换主串 s 中出现的所有与t 相等的不重叠的子串。则执行replace(s

16、1,Substr(s1,4,length(s3),s3)，Concat(s1,Subsb(s4,index(s2,8),length(s2)后，其结果是 ( )。A.ABC#G0123 B ABCD#2345 C ABCD#1234 DABC#G1234 6一棵深度为k 的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。A.2k-1-1 B.2k-1C.2k-1 D.2k7按照二叉树的定义，具有3 个结点的二叉树有 ( )种。 A3 B4 C5 D6 8由带权为 8，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（） 。 A 23 B37 C46 D43

17、9具有 4 个顶点的无向完全图有 ( )条边。 A6 B12 C16 D20 10树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、 中序遍历和后序遍历。 这里，把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是( )。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D 以上都不对11栈和队列的共同点 ( )。 A 都是先进后出 B都是先进先出C只允许在端点处插入和删除元素 D没有共同点12深度为 5 的二叉树至多有 ( )个结点。 A16 B3

18、2 C31 D10 13关键路径是事件结点网络中的( )。A从源点到汇点的最长路径 B从源点到汇点的最短路径C 最长的回路 D最短的回路14每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间元素的关键字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 均大于基准元素的关键字，则此排序方法叫做( )。 A 插入排序 B快速排序 C归并排序 D选择排序15对线性表进行折半查找时，要求

19、线性表必须( )。 A以顺序方式存储 B以顺序方式存储， 且结点按关键字有序排序 C以链接方式存储 D以链接方式存储， 且结点按关键字有序排序二、填空题（每空2分，共 30分）1数据逻辑结构包括、三种类型。2队列是只允许在表的进行插入操作， 而在进行删除操作的线性表，栈是限定仅在进行插入或删除操作的线性表。3在程序段 s=0；for (i=0 ；in ；i+) for (j=0 ；jm；j+) s+=aij；中，时间复杂度为。4归并排序法稳定的内部排序方法。5在一棵二叉树中，度为0 的结点个数为 n0，度为 2 的结点个数为 n2，则 n0 = 。6树所对应的二叉树其根结点的子树一定为空。7试

20、举出两种常用的查找方法，。8. n 个顶点的连通图至少有条边。9. 在一棵二叉排列树上按遍历得到的结点序列是一个有序序列。10. 在一个图 G的邻接表表示中， 每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的。三、简答题（共30分）1、 已知二叉树的层次和中序遍历序列分别如下：层次： ABCDEFGHIJ 中序： DBGEHJACIF (1) 构造出该二叉树（ 5 分）(2) 画出该二叉树的先序线索化（5 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11

21、 页 - - - - - - - - - 3、已知有向图如下图，求每个顶点的入出度，并给出该图的邻接矩阵。（10分）4、设权 W=7 ，18，2，6，32，3，21，10，试把它们作为叶子结点的权值，构造一棵哈夫曼树，并求出其带权路径长度（WPL ） （10 分）四、程序算法（共10 分）对任意输入的一个非负十进制整数，打印输出其二进制数，要求写出算法以及栈的结构定义（顺序，链式都可以） 。一、选择（共 30 分）123456789101112131415BBCBDCCDAACCABB二、填空（每题 2 分，共 30 分）1、线性结构，树状结构，图状结构 2、末端，队头，栈顶3、 O（n*m）

22、 4、是 5、n2+1 6、 右 7、顺序查找， 折半查找 （索引顺序表查找，二叉排序树查找等）8、 n-1 9、 中序 10、出度三、应用（30 分）1、5 分先序序列ABDEGHJCFI 2 分线索化 3 分B D C E F A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 2、顶点入度出度A03B12C31D11E21F12G20入 度 3 分， 出 度 3 分 ，共6 分邻接 矩 阵4 分 每两行 1分3、哈夫曼树

23、（ 6 分） ： WPL （4 分）: 7 4+182+25+64+322+35+212+104=259 四、算法程序typedef struct selemtype *base; Selemtype *top; 1 2 3 3 1 2 3 1 2 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - sqstack; 写出结构定义给 5 分Void conversion() initstack(S); Scanf(“ %d ” ，N); While (N) push(S,N % 2); N=N/2; While(! StackEmty(S) pop( S,e ); Printf(“ %d ” ,e); 算法给 10 分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -