2022年数据结构试题试题及答案归类 .pdf

1 一、单选题（每小题2 分，共 8 分）1. 在一个长度为 n 的线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度（即 x 同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2。以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树3. 若有 18 个元素的有序表存放在一维数组A19 中，第一个元素放A1 中，现进行二分查找，则查找A3的比较序列的下标依次为( D ) A. 1，2，3 B. 9 ，5，2，3 C. 9，5，3 D. 9 ，4，2，3 4. 设有 6个结点的无向图，该图至少应有( A) 条边才能确保是一个连通图。A.5 B.6 C.7 D.8 5在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn) ，最坏情况下时间复杂度为 0(n2) ；（ d ）方法所有情况下时间复杂度均为0(nlogn) 。a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序6具有 m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。a. log 2 m b. log2 m +1 c. m/2 d . m/2 -1 e. m/2 f. m 7下列排序方法中，属于不稳定的排序方法是(A ) A. 直接插入排序法 B.冒泡排序法C.基数排序法 D.归并排序法8 在最好和最坏情况下的时间复杂度均为O(nlogn) 且稳定的排序方法是( C ) A. 快速排序 B.堆排序C.归并排序 D.基数排序9 设有一个二维数组A m n ，假设 A00存放位置在 644(10)，A22存放位置在 676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用 10 进制表示。 A688 B678 C692 D696 10 由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） A 24 B 71 C 48 D 53 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 2 11，某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B ）的 二叉 树。 A、空或只有一个结点 B、高度等于其结点数 D、任意结点无右孩子 C、任意结点无左孩子12 将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为 1，则编号为49 的结点的左孩子的编号为_A_。A.98 B.99 C.50 D.48 13. 设有 100 个元素，用折半查找法进行查找时，最大比较次数是_D_ 。A.25 B.50 C.10 D.7 14. 在含有 n 个项点有 e 条边的无向图的邻接矩阵中，零元素的个数为_D_。A.e B.2e C.n2-e D.n2-2e 15. 图的深度优先遍历类似于二叉树的_A_。A.先序遍历 B.中序遍历C.后序遍历 D.层次遍历16. 设长度为n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_C_。A. O(1) B. O(log2n) C. O(n) D. O(n2) 17. 在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是_B_ AO（1） B.O（n）C.O(nlogn) D.O(n2) 18队和栈的主要区别是_D_ A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同19链栈与顺序栈相比，比较明显的优点是_D_ A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况20在目标串T0 n-1= ”xwxxyxy ”中，对模式串p0 m-1= ”xy”进行子串定位操作的结果_C_ A.0 B.2 C.3 D.5 21已知广义表的表头为A，表尾为 (B,C) ，则此广义表为_B_ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 3 A.（A,(B,C) ） B. （ A,B,C）C.(A,B,C) D.( A,B,C) 22 二维数组 A按行顺序存储， 其中每个元素占1 个存储单元。 若 A11的存储地址为420，A33的存储地址为446，则 A55的存储地址为 _C_ A.470 B.471 C.472 D.473 23. 向堆中插入一个元素的时间复杂度为_A_。A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n) 24. 用某种排序方法对关键字序列（25，84，21，47，15， 27，68，35， 20）进行排序时，序列的变化情况是如下_D_： 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.快速排序25. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址_D_ 、必须是连续的、部分地址必须是连续的、一定是不连续的、连续不连续都可以二、填空题（每空 1 分，共 32 分）1 数据的逻辑结构被分为 _集合_、 _ 线性_ 、 _树_和_图_四种。2 假定一棵树的广义表表示为A（C ，D （E，F，G ），H （I ，J），则树中所含的结点数为 _9_个，树的深度为 _3_，树的度为 _3_。3 对于一个具有 n个顶点和 e条边的有向图和无向图， 在其对应的邻接表中，所含边结点分别有 _e_个和_2e_ 个。4 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O （log2 n ）_，整个堆排序过程的时间复杂度为_O （nlog2 n ）_。5 一棵高度为 5 的二叉树中最少含有 _5_ 个结点，最多含有 _31_ 个结点；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 4 一棵高度为5 的理想平衡树中，最少含有_个结点，最多含有_个结点。6 设有一个顺序共享栈S0：n-1 ，其中第一个栈项指针top1 的初值为-1 ，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是 （top1+1=top2 ）三 判断题3、（1）线性表的逻辑顺序与物理顺序总是一致的。（2）线性表的顺序存储表示优于链式存储表示。（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（4）二维数组是其数组元素为线性表的线性表。（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。（1）错（ 2）错（ 3）对（ 4）错（ 5）对6 如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入上 去，一定能得到原来的二叉排序树。( CUO) 7 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（ CUO ）8、直接选择排序是一种不稳定的排序方法。（ CUO ）9、在只有度为0 和度为 k 的结点的 k 叉树中，设度为0 的结点有n0 个，度为k 的结点有nk 个，则有 n0=nk+1。 （ CUO ）10、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（ CUO ）四，应用题1已知 Hash函数为 H（K）=K mod 13 ，散列地址为 0 -14 ，用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49, 52 ，36，92，06，55）在散列地址的分布。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2. 右图为一棵 3 阶 B 树。（20，25）a. 画出在该树上插入元素15后的 B 树。 b. 接着，再删除元素35，画出删除后的B 树。 (10,14)（21）（35） 4. 已知某无向图的邻接表存储结构如图所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 5 a. 请画出该图。b. 根据存储结构给出其深度优先遍历序列及广度优先遍历序列。c. 画出其深度优先生成树及广度优先生成树。0 a 2 4 / 1 b 2 3 4 / 2 c 0 1 4 / 3 d 1 / 4 e 0 1 2 / 3、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。（1）对于一个具有n 个结点和 e 条边的无向图，若采用邻接表表示，则顶点表的大小为（ A），所有边链表中边结点的总数为（B）。（2）采用邻接表存储的图的深度优先遍历算法类似于树的（C）。（3）采用邻接表存储的图的广度优先遍历算法类似于树的（D）。（4） 判断有向图是否存在回路， 除了可以利用拓扑排序方法外， 还可以利用（E） 。供选择的答案A：nn+1n-1n+e B：e/2 e2en+e CD ：中根遍历先根遍历后根遍历按层次遍历E：求关键路径的方法求最短路径的Dijkstra方法深度优先遍历算法广度优先遍历算法4假定线性表 L=（33,85,21,56,30,63,42,91,76）, 调用顺序表的排序算法void Sort(List& L)对此表进行排序，请写出排序过程。（将每一步结果写出）（1） 33 85 21 56 30 63 42 91 76 （2） 21 33 85 56 30 63 42 91 76 （3） 21 33 56 85 30 63 42 91 76 （4） 21 30 33 56 85 63 42 91 76 （5） 21 30 33 56 63 85 42 91 76 （6） 21 30 33 42 56 63 85 91 76 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 6 （7） 21 30 33 42 56 63 85 91 76 （8） 21 30 33 42 56 63 76 85 91 2、下图所示的森林：(1) 求树（ a）的先根序列和后根序列；(2) 求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)2(1) ABCDEF; BDEFCA ；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；AGBCDEFHIJK六编程题1 设计在二叉排序树上查找结点X的算法。bitree *bstsearch1(bitree *t, int key) bitree *p=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; return(0); 2 写出向二叉排序树中插入一个元素的非递归算法。Void insert(BtreeNode * BST, const ElemType & item) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 7 BtreeNode *t=BST, *parent=NULL; While(t!=NULL) Parent=t; If(itemdata) t=t-left; Else t=t-right; BtreeNode *p=newBtreeNode; p-data=item; p-left=p-right=NULL; if(parent= =NULL) BST=p; else if(itemdata) parent-left=p; else parent-right=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -