2022年数据结构终版 .pdf

《2022年数据结构终版 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构终版 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、题 1.1 数据结构在计算机内存中的表示是指 。A数据的存储结构B数据元素C数据的逻辑结构D数据元素之间的关系题 1.2 从逻辑上可把数据结构分为 。A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性存储结构D.内部结构和外部结构题 1.3 判断正误：数据元素是数据的最小单位。题 1.4 分析下列程序段的时间复杂度：(1) x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; (2) for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; (3) i=1; while (

2、i=n) i=i*2 (4) i=0; s=0; while(sn) i=i+1; s=s+i; 题 1.5 设 n 是偶数，试计算运行下列程序段后m 的地址并给出该程序段的时间复杂度。m=0；for(i=1;i=n;i+) for(j=2*i;j=n;j+) m=m+1; 题 2.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 线性表的静态链表存储结构与顺序存储结构相比优点是。A所有的操作算法实现简单B便于随机存取C. 便

3、了插入和删除D便于利用零散的存储器空间题 2.2 判断正误1.顺序存储只能用于存储线性结构2.顺序查找法适用于存储结构为线性或链接存储的线性表。题 2.3 若较频繁地对一个线性表进行插入和删除操作，该线性表宜用什么存储结构，为什么？题 2.4 线性链表中各链接点的位置 。A必须连续B部分地址必须连续C. 不一定连续D连续与否无所谓题 2.5 线性表是具有n 个（ ）的有限序列。(1)表元素(2)字符(3)数据元素(4)数据项(5)信息项题 2.6 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个元素的时间复杂度为（1= i next=q ，q-prior=p) ，请写出删除q 所

4、指向结点的程序段。题 2.9 将 两 个 各 有n 个 元 素 的 有 序 表 归 并 成 一 个 有 序 表 ， 其 最 小 的 比 较 次 数是。A.n B.2n-1 C.2n D.n-1 题 2.10 填空：在一个单链表的p 结点之前插入一个人结点s时，可执行如下操作：(1)s-next = ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - (2)p-next = s; (3)t = p-data; (4)p-data

5、= ; (5)s-data = ; 题 2.11 带头结点的双向循环链表L 为空表的条件是。题 2.12 需要分配较大存储空间，插入和删除不需要移动元素的线性表，其存储结构是。A.单链表B.静态链表C.线性链表D.顺序存储结构题 2.13 有一个单链表L，其结点的元素值以非递减有序排列，编写算法删除该单链表中多余的元素值相同的结点。题 2.14 有一个单链表L(至少有一个结点)，其头结点指针为L，编写一个过程将L 置逆， 要求逆转在原链表上进行题 3.1 若用一个大小为6 的数组来实现循环队列，且当前rear 和 front 的值分别为0 和 3。当从队列删除一个元素，再加入两个元素后，rea

6、r 和 front 的值分别为。A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1 题 3.2 用数组表示的循环队列的队首位置和队尾位置分别为1 和 max_size，试给出判断队列为空和满的条件(队列长度最大为MAXSIZE) 。题 3.3 若某堆栈的输入序列为1,2,3, ,n，输出序列的第一个元素为n，则第i 个输出元素为。A.i B.n-i C. n-i+1 D.哪个元素无所谓题 3.4 设栈的输入序列是1,2,3,4，则不可能是其出栈顺序。A. 1243 B.2134 C.1432 D.4312 E.3214 题 3.5设输入元素为1、2、3、P 和 A，输入次序为123

7、PA。元素经过栈后到达输出序列，当所有元素都到达输出序列后，有哪些序列可作为高级语言的变量名。题 3.6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 设栈 S 和队列 Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后即进入队列Q。若这 6 个元素出队列的顺序是b、d、c、f、e、a，则栈的容量至少为？题 3.7用数组 Q(其下标在0 n-1，共有 n 个元素 )表示一个循环队列，f 为当前对头元素

8、的前一位置， r为队尾元素位置，假定队列中元素个数总小于n，求队列中元素个数的公式是。题 4.1 是 C 语言中 “ abcd321ABCD ” 的子串。Aabcd B321AB C. “ abcABC ”D“ 21AB ”题 4.2 字符串满足为下式，其中Head 和 Tail 的定义与广义表类似，则S= 。Contact(Head(Tail(S), Head(Tail(Tail(S) = “dc”A. abcd B.acbd C.acdb D.adcb 题 4.3 设 S 为一个长度为n 的字符串，其中的字符各不相同，则S 中的互异的非空子串(不含 S本身 )的个数是。A.2n-1 B.n

9、2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E.(n2/2)+(n/2)+1 题 4.4 若串 S = “ software”，其非空子串数目为（） 。A8 B37 C. 36 D9 题 4.5 填空：两个串相等的充分必要条件是。题 4.6 空串和空格串的区别是？题 5.1 填空：设有上三角矩阵A(aij )n*n，将其上三角元素逐行存于数组B1 m中(m 充分大)，使得 Bk=aij，则 k= 。题 5.2 数组 a 中，每个元素ai, j 的长度为 3 个字节，行下标i 从 0 到 7，列下标j 从 0 到 9，从首地址连续存放在存储器内，该数组按行优先存放时，元素

10、 a74 的起始地址为. A.a+141 B.a+144 C.a+222 D.a+225 题 5.3 填空：已知10 行 20 列的二维数组A 按行优先方式存放，每个元素占一个存储单元，并且名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - A00 的存储地址是200，则A511 的地址是；如果该数组按列优先方式存放，则 A511 的地址是。题 5.4 填空：有一个10 阶对称矩阵A，采用压缩存储方式(以行序位主序且A00 地址为1

11、)，则 A74 的地址为。题 5.5 填空：将一个A0.99, 0.99的三对角矩阵，按行优先存入一维数组B0.297 中， A中元素 A6564 在 B 中的位置k 为。题 5.6 若广义表A 满足 Head(A) = Tail(A) ，则 A 为。A.( ) B.( ) C.( ), ( ) D.( ), ( ), ( ) 题 5.7 设广义表L = ( ), ( )，则 Head( L)= ，Tail( L)= ，L 的长度是，L 的深度是。题 6.1 设高度为h 的二叉树上只有度为0 和度为 2 的结点，则此二叉树中所包含的结点数至少为，至多为。A.2h B.2h-1 C.2h+1 D

12、.h+1 E.2h-1 F.2h-1 G.2h+1 H.2h+1+1 题 6.2 某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，画出该二叉树，并求其后序遍历序列。题 6.3 若一个具有n 个顶点， k 条边的无向图是一个森林(NK), 则该森林中必有颗树。A.k B.n C.n-k D. 1 题 6.4 填空：深度为k 的完全二叉树至少有个结点，至多有个结点， k和结点 n 的关系为。题 6.5 填空：一棵有100 个叶子结点的完全二叉树，最多有结点。题 6.6 具有 n 个结点的满二叉树，其叶子结点有个。名师资料总结 - - -精品资料欢迎下载 - - - - -

13、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 题 6.7 已知某字符串S 共有 8 种字符，各种字符分别出现2 次、1 次、4 次、5 次、 7 次、 3次、 4 次和 9 次，对该字符串用0, 1 进行前缀编码，问该字符串的编码至少有多少位。题 6.8 填空：有 n 个结点的二叉树，已知叶子结点个数为n0，写出求度为1 的结点的个数n1 的计算公式；若二叉树中仅有度为0 和度为2 的结点，写出求该二叉树结点个数n 的公式。题 6.9 请编写一个函数 （int LeafCount（Bi

14、nary_tree BT ） ） ，求此二叉树的叶子结点个数。有关的数据结构已描述如下：typedef struct /二叉树结点int data; Binary_node *lchild; Binary_node *rchild; Binary_node ，*Binary_tree; 题 6.10 已知某系统在通信联络中只可能出现八种字符（a，b，c，d，e，f，g，h） ，其概率分别为 5%, 29%, 7%, 8%, 14%, 23%, 3%, 11%，试设计对应Huffman 树，根据此Huffman 树写出每个字母的赫夫曼编码。题 7.1 给出该图的邻接矩阵、邻接表、逆邻接表。题 7

15、.2 设无向图的顶点个数为n，则该无向图最多有条边。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D. n2 题 7.3 G 是一个连通图，共有28 条边，则该图至少有个顶点，如果G 是非连通的，则该图至少有个顶点。A.6 B.7 C.8 D.9 题 7.4 Kruskal 算法的时间复杂度是，它对图较为合适。题 7.5 用 Prim 算法（从顶点1 出发）和Kruskal 算法分别构造图G 的最小生成树。题 7.6 对于如图所示的事件结点网络，求出各活动可能的最早开始时间和最晚完成时间，并问哪些活动是关键活动。名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

16、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 题 9.1 对长度为 12 的递增有序表 （a1,a2, ,a12）进行折半查找， 在设定查找不成功时，关键字 xa12 以及 aixai+1(i=1,2,11) 等情况发生的概率相等，则试分析查找不成功的平均查找长度是多少。题 9.2 若在线性表中采用折半查找法，该线性表应该（） 。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构题 9.3 已知序列17，31，13， 11，20，35，25

17、，8，4，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉树：1)插入数据9，2)删除结点17。题 9.4 含有 12 个结点的平衡二叉树的最大深度是（设根结点深度为1） 。题 9.5 在非空 m 阶 B-树上，除根结点以外的所有其他非终端结点。A.至少含有m/2 棵子树B.至多含有m/2棵子树C.至少含有m/2 棵子树D.至多含有m/2棵子树题 9.6 使用哈希函数H(x)=x%11 把一个整数值转换成散列表下标，现要把数据1、13、12、34、38、 33、27、22 插入到散列表，画出使用线性探测再散列构造的散列表。题 9.7 已知序列45，15，20，35，25，

18、 60，18，50，请画出依次插入该序列的的AVL 树。题 10.1 在下列方法中，所需辅助存储量最多的是，所需辅助存储量最少的是，平均速度最快的是。A.快速排序B.归并排序C.堆排序2431a1=4a5=6a3=2a2=3a4=4名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 题 10.2 在文件 “ 局部有序 ” 的情况下，最佳内部排序是。A.直接插入排序B.快速排序C.简单选择排序题 10.3 快速排序在最坏情况下时间复杂度是O(n2)，比的性能差。A.堆排序B.起泡排序C.选择排序题 10.4 若需在 O(nlog2n) 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的方法是。A.快速排序B.堆排序C.归并排序D.直接插入排序题 10.5 判别序列（ 12，70，33，65，24，56，48，92，86，33）是否为小顶堆，如果不是，则把它调整为小顶堆。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -