《2022年数据结构中考试题.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构中考试题.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学号姓名密封线密封线一、单项选择题（本大题共13 小题，每小题1 分，共 13 分，请将正确选项前的字母填在下列表格的相应位置。）题号1 2 3 4 5 6 7 8 9 10 11 12 13 答案A D D C B B B C D A B B D 1、算法的时间复杂度与 _ 有关。(A) 问题规模 (B) 计算机硬件性能 (C) 编译程序的质量 (D) 程序设计语言2、在线性表的下列存储结构中，读取元素花费时间最少的是_。(A) 单链表 (B) 双链表 (C) 循环链表(D) 顺序表3、线性表采用链式存储结构时，其地址_。(A) 必须是连续 (B) 一定是不连续 (C) 部分地址必须是连续(
2、D) 连续与否均可4、设有一栈，元素依次进栈顺序为a，b，c，d，e。下面 ( ) 是不可能的出栈（A）abcde （B）bcdeab （C）eabcd （D）edcba, 5、串是一种特殊的线性表，其特殊性体现在_。(A) 可以顺序存储 (B) 数据元素是一个字符(C) 可以链接存储 (D) 数据元素可以是多个字符6、对矩阵压缩存储是为了 _。(A) 方便运算 (B) 节省空间 (C) 方便存储 (D) 提高运算速度7、将递归算法转换成对应的非递归算法时，通常需要使用 _保存中间结果。(A) 队列 (B) 栈 (C) 链表 (D) 树8、二叉树若用顺序方法存储，则下列4 种运算中的 _最容易
3、实现。(A) 先序遍历二叉树 (B) 判断两个结点是否在同一层上(C) 层次遍历二叉树 (D) 根据结点的值查找其存储位置9带头结点的单链表head 为空的判断条件是（）(A)head = =NULL (B)head! =NULL 9 - (C)head-next= =head (D)head-next= =NULL 10. 在单链表中，指针p 指向结点 A，若要删除 A 之后的结点（存在），则指针的操作方式为 ( )。A. p- next= p- next- next; B. p= p- next; C. p= p- next- next; D. p- next=p;%11设 C 语言数组
4、Datam 作为循环队列的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作的语句是( )。Y! A. front=front+1; B. front=(front+1)%m;+ c/ + oC. rear=reart+1; D. rear=(reart+1)%m;12. 若一棵二叉树具有10个度为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点个数是（）。 H2 H A. 9 B.11 C. 15 D. 不确定13n 个结点的线索二叉树上含有的线索数为（） 。* S0 i A. n B. 2n C. n l D. n l2 二、判断题 (每小题 1 分，共
5、12 分。判断下列各题，正确的打“” ，错的打“”，请将答案填在下列表格的相应位置。) 题号1 2 3 4 5 6 7 8 9 10 11 12 答案1单链表中的头结点就是单链表的第一个结点。2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。3、二叉排序树中，新结点总是作为树叶来插入的。4、 在用循环单链表表示的链式队列中，可不设队头指针，仅在链尾设置队尾指针。5、在哈夫曼树中，权值相同的树叶结点都在同一层上。6、二叉树就是结点度为2 的树。7、栈底元素和栈顶元素有可能是同一个元素。8、无论是顺序队列还是链接队列，插入、删除运算的时间复杂度都是O(1)。9、线性表的顺序存储结构优于链
6、式存储结构。10、对于单链表来说，只有从头结点开始才能扫描表中全部结点。11、用非递归方法实现递归算法时一定要使用递归工作栈。12. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 5 页 - - - - - - - - - - 学号姓名密封线密封线三、应用题（本大题共2 小题，共 15 分）1、已知一棵二叉树的中序序列是CBEDAHGIJF，后序序列为 CEDBHJIGFA，请画出该二叉树，
7、并写出该二叉树先序序列。解：该二叉树如下图：其先序序列是：ABCDEFGHIJ 。（评分标准：正确画出图， 5 分，正确写出先序序列，3 分）2、设给定权集散地W=2 ，3，4，7，8，9 ，试构造关于 W的一棵哈夫曼树，并求其加权路径长度 WPL 。解： 解：设这8 个字母所对应的权值分别为（5，25，4，7，9，12，30，8） ，并且 n=8。（1）赫夫曼树为： （4 分）（2）在上面求出的赫夫曼树中规定左分支表示“0” ，右分支表示“1” （如右图所示） ，则可以构造赫夫曼编码为：A:0011 B:01 C:0010 D:1010 E:000 F:100 G:11 H:1011（4 分
8、）其加权路径长度WPL=(9+7+8)*2+4*3+(2+3)*4=80 ( 评分标准：正确画出图，给5 分；正确计算WPL ，给 3 分；若不完全正确则酌情给分) 四. 算法设计题： (每题 8 分，共 5 小题，共计 40 分) 1、设计一个算法，将x 插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。解：存储结构如下：typedef struct SqList ElemType *elem; int length; int listsize; SqList; 算法如下：void InsertOrderSqList(SqList &L, ElemTyp
9、e x) int k=L,length-1; while(k=0 & xnext; H-next=0; while(p) q=p; p=p-next; q-next=H-next; H-next=q; (评分标准：正确写出存储结构可给2 分，算法正确给6 分，不完全正确则酌情给分) 3、已知一个不带头结点的单链表head，结点结构为 Node 。写出一个通用的算法，删除链表中值相同的结点（如果有值相同的结点只保留首次出现的结点）。例如，删除前： y head& 删除后： Fhead 2 G# D; r8 z J, 预编译命令： # define NULL 0 /NULL 表示空指针结点结构：t
10、ypedef struct node7 2 b( m+ J1 % H9 d4 int data; struct node *next; * X I* J# P8 Node; + V O! u/ B- ) d7 Z解：Node * Expurgate (Node * head)Node *p,*q,*q0; 3 b q! j; S3 G( W: X/1 分p=head; /2 分while(p) /3 分 q0=p; q=p-next; /4 分while(q) /5 分2 T G9 s: Q; X+ % L5 if(p-data!=q-data) /6 分9 l( a4 w* x(q0=q;
11、q=q0-next; /7 分2 y9 I7 I( D z else # G( d7 D1 d& - O+ V# o9 T& 通八达q0-next=q-next; q=q0-next; /8 分 p=p-next; /9 分 + V) L( y% p* , L s! j# w! W0 ( b return(head); /10 分 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 5 页 - - - - - - - - - - 学号姓名密封线密封4、假定二叉树采用二叉链存储结构存储，试设计一个算
12、法，计算一棵给定二叉树的所有结点的个数。解：存储结构如下：typedef struct BiTNode ElemType data; struct BiTree *left, *right; BiTNode, *BiTree; 算法如下：int Nodes(BiTree &T) if(!T) return 0; else return Nodes(T-left)+Nodes(T-right)+1; (评分标准：正确写出存储结构可给2 分，算法正确给6 分，不完全正确则酌情给分，算法可以写成递归算法，也可以写成非递归算法) 5、假设二叉树采用二叉链表存储结构存储，设计一个算法，删除该二叉树，并释
13、放所有的结点。解：存储结构如下：typedef struct BiTNode ElemType data; struct BiTree *left, *right; BiTNode, *BiTree; 算法如下：void DeleteBiTree(BiTree &T) if(!T) return; else DeleteBiTree(T-left); DeleteBiTree(T-right); delete(T); T=0; (评分标准：正确写出存储结构可给2 分，算法正确给6 分，不完全正确则酌情给分，算法可以写成递归算法，也可以写成非递归算法) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 5 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 5 页 - - - - - - - - - -