数据结构与算法[参考文章]

《数据结构与算法[参考文章]》由会员分享，可在线阅读，更多相关《数据结构与算法[参考文章]（54页珍藏版）》请在装配图网上搜索。

1、试题分类：数据结构与算法1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。A.操作B.存储映像C.关系D.数据元素答案:C题型:单选题知识点:1.2 基本概念和术语难度:12.一般而言，最适合描述算法的语言是( )。A.自然语言B.计算机程序语言C.介于自然语言和程序设计语言之间的伪语言D.数学公式答案:C题型:单选题知识点:1.4 算法和算法分析难度:13在下列序列中，不是线性表的是( )。A. (a, b)B. (a, b)C. (AB, CD)D. (a, b)答案:D题型:单选题知识点:2.1 线性表的类型定义难度:24.对于顺序表的优缺点，以下说法错误的是( )。A

2、.插入和删除操作较方便B.可以方便地随机存取表中的任一结点C.无需为表示结点间的逻辑关系而增加额外的存储空间D.由于顺序表要求占用连续的空间，存储分配只能预先进行题型:单选题知识点:2.2线性表的顺序表示和实现难度:25.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。A. s-next=p-next;p-next=s;B. p-next=s-next;s-next=p; C. q-next=s;s-next=p; D. p-next=s;s-next=q;题型:单选题知识点:2.3线性表的链式表示和实现难度:26.若某链表中最常用的操作是在最后一

3、个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。A.单链表B.带头结点的单链表C.单循环链表D.带头结点的双循环链表题型:单选题知识点:2 线性表难度:37.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )。A. edcbaB. decbaC. dceabD. abcde题型:单选题知识点:3.1 栈难度:18.设有循环队列Q，已知MAXQSIZE=18，Q.front=12，Q.rear=14，在连续执行了3次入队，2次出队，3次入队操作之后，(Q.front, Q.rear)的值为( )。A. (13, 0)B. (14, 2)C. (13, 1

4、7)D. (14, 17) 题型:单选题知识点:3.4 队列难度:39.对于稀疏矩阵的压缩存储只需存储( )。A.零元素 B.非零元素C.对角线上的元素D.所有元素题型:单选题知识点:5.3 矩阵的压缩存储难度:110.对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。A. 先序遍历B. 中序遍历C. 后序遍历D. 从根结点开始的层次遍历题型:单选题知识点:6.3 遍历二叉树和线索二叉树难度:211.设一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当采用折半查找值为95的

5、结点时，( )次比较后查找结束。A. 2B. 3C. 4D. 5题型:单选题知识点:9.1 静态查找表难度:212.如果表中有100000个元素，前99999个元素递增有序，则采用( )排序方法比较次数较少。A. 快速排序B. 直接选择排序C. 冒泡排序D. 直接插入排序题型:单选题知识点:10 内部排序难度:113. 数据的最小单位是_。答案: 数据项题型:填空题知识点:1.2 基本概念和术语难度:114.数据的存储结构包括顺序、链式、索引和_四种基本类型。答案: 散列题型:填空题知识点:1.2 基本概念和术语难度:115.设L是带有头结点的单链表的头指针，则判断单链表为空的条件是_。题型:

6、填空题知识点:2.3 线性表的链式表示和实现难度:216.在单链表中，头结点的作用是_。题型:填空题知识点:2.3 线性表的链式表示和实现难度:217.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以C第一个出栈、D第二个出栈的次序有_种。题型:填空题知识点:3.1 栈难度:218. _可以作为实现递归函数的一种数据结构。题型:填空题知识点:3.2 栈的应用举例难度:119. 在队列中，可进行删除操作的一端称为_。题型:填空题知识点:3.4 队列难度:120. 对于一个具有7个结点的二叉树，当它为一棵_二叉树时具有最小高度。题型:填空题知识点: 6.2 二叉树难度:121

7、. 设广义表为(a, (b), (c, (d)，则表长为_。答案: 3知识点:5.4 广义表的定义难度:122. 邻接表是图的_存储结构。题型:填空题知识点: 7.2图的存储结构难度:123. 若无向图中有n个结点，e条边，则它的邻接表需要_个表结点。答案: 2e知识点:7.2 图的存储结构难度:124. _排序方法能够每次从无序表中顺序查找出一个最小值。答案: 简单选择排序知识点:10 内部排序难度:125.设有如图所示的逻辑结构图，请给出数据结构形式。1234答案: 数据结构可形式地定义为（D，S）D=1，2，3，4S=RR=, , , , 题型:计算题知识点:1.2 基本概念和术语难度:

8、126.请用C语言给出顺序栈(栈的顺序存储结构)的类型定义。题型:简答题知识点:3.1 栈难度:127. 依据下面的有向图回答问题。V1V2V3V4(1) 请给出每个顶点的度、入度和出度。(2) 请给出其邻接表。题型:计算题知识点:7 图难度:228设有一个输入数据的序列是46，25，78，62，12，70，29，画出逐个输入各个数据而生成的二叉排序树。题型:计算题知识点:9.2 动态查找树难度:129. 以关键字序列12，2，16，9，10，8，20为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。(1)直接插入排序(2)快速排序上述方法中，哪个是稳定的排序？哪个是不稳定的排

9、序？题型:计算题知识点:10 内部排序难度:230. 阅读如下算法，给出该算法的功能，并给出算法执行结束后，链表L的示意图。void Unkown(LinkList &L, int n) L=（LinkList）malloc(sizeof (LNode); L-next=NULL;for (i=n; i0;-i) p=(LinkList)malloc(sizeof(LNode); p-data=i;p-next=L-next;L-next=p; 题型:算法题知识点:2.3 线性表的链式表示和实现难度:331.在长度大于1的带头结点的单链表中，p为指向待处理结点的指针，pre为指向最小值结点的前

10、驱结点的指针。下面算法的功能是：删除最小值结点。请在空缺处填入相应的语句。void Delete(LinkList &L) p = L-next; pre = L;q=p;while( (1)_) if (p-next-data data) (2)_; (3)_;(4)_; pre-next = q-next;free(q);题型:算法题知识点:2.3 线性表的链式表示和实现难度:232. 数据结构在计算机内存中的表示是指( )。A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据结构答案:B题型:单选题知识点:1.2 基本概念和术语难度:133. 在数据结构中，从逻辑上可

11、以把数据结构分为( )。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构答案:C题型:单选题知识点:1.2 基本概念和术语难度:134. 对一个有127个元素的顺序表中删除一个元素，平均要移动( )个元素。A.62B. 63C. 63.5D. 64题型:单选题知识点:2.2 线性表的顺序表示和实现难度:235. 线性表若采用链式存储结构，要求内存中可用存储单元的地址( )。A.必须是连续的B.部分必须是连续的C.一定是不连续的D.连续不连续都可以题型:单选题知识点:2.3 线性表的链式表示和实现难度:236. 在一个单链表中，若删除p所指结点的后继结

12、点，则执行( )。A. q = p-next; p-next = q-next; free(q);B. p = p-next; p-next = p-next-next; free(p);C. p-next = p-next; free(p-next);D. p = p-next-next; free(p-next);题型:单选题知识点:2.3 线性表的链式表示和实现难度:237. 设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。A. 1B. 2C. 3D. 4题型:单选题知识点:3.1 栈难度:238. 在顺序

13、栈S中插入元素e时，执行( )。A. *S.top = e; S.top+;B. S.top+; *S.top = e;C. *S.top = e; S.top-;D. S.top-; *S.top = e;题型:单选题知识点:3.1 栈难度:239. 设有一个二维数组A1020，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，则元素A66的存放位置为( )。A. 320(十进制)B. 232(十进制)C. 300(十进制)D. 352(十进制)题型:单选题知识点:5.2 数组的顺序表示和实现难度:240. 某二叉树的先序遍历序列与后序遍历序列相反，则此

14、二叉树一定是( )。A. 高度等于其结点数B. 空或只有一个结点C. 任一结点无左孩子D. 任一结点无右孩子题型:单选题知识点:6.3 遍历二叉树和线索二叉树难度:341. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A. 5B. 6C. 7D. 8题型:单选题知识点:7.1 图的定义和术语难度:242. 在哈希函数H(key) = key%m中，一般来说，m应取( )。A. 奇数B. 偶数C. 素数D. 充分大的数题型:单选题知识点:9.3 哈希表难度:143. 下列序列中，( )才可能是执行第一趟快速排序后得到的序列。A. 8，6，10 19 16，20，18B. 8

15、0，1，2 36 46，90，37C. 6，7，8 18 81，20，36，18D. 2，3 89 100，78，90题型:单选题知识点:10.3 快速排序难度:244. 在线性表中，一个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为_。答案: 记录题型:填空题知识点:1.2 基本概念和术语难度:145. 数据的基本单位是_。答案:数据元素题型:填空题知识点:1.2 基本概念和术语难度:146. 在单链表中，头指针的作用是_。答案:用于标识单链表题型:填空题知识点:2.3 线性表的链式表示和实现难度:2 47. 在一个双向循环链表中，删除p所指结点，则执行_。题型:填空题知识点:2

16、.3 线性表的链式表示和实现难度:248. 在队列中，新插入的结点只能添加到_。 题型:填空题知识点:3.4 队列难度:149. 广义表(a), (b)的表头是_。题型:填空题知识点:5.4 广义表的定义难度:150. 深度为5的满二叉树的结点数为_。题型:填空题知识点:6.2 二叉树难度:151. 按二叉树的定义，具有4个结点的二叉树有_种。题型:填空题知识点:6.2 二叉树难度:252. Prim算法适用于边数较_的图。题型:填空题知识点:7.4 图的连通性问题难度:253. 已知一个有向图的邻接矩阵表示，则计算第i个结点的出度的方法是_。题型:填空题知识点:7.2 图的存储结构难度:25

17、4. 折半查找的存储结构仅限于_存储结构。题型:填空题知识点:9.1 静态查找表难度:155. 具有20个记录的序列，采用起泡排序最多的比较次数为_。题型:填空题知识点:10.3 快速排序难度:256. 请用C语言给出顺序表(线性表的顺序存储结构)的类型定义。答案:typedef struct ElemType *elem;int length;int listsize;SqList;题型:简答题知识点:2.1 线性表的顺序表示和实现难度:157. 对于线性表的顺序存储结构，设起始地址为66，每个元素占5个存储单元，求第12个元素的内容存储在哪几个存储单元中。题型:计算题知识点:2.2 线性表

18、的顺序表示和实现难度:158. 将如下树转换成二叉树。ABEFCGD题型:计算题知识点:6.4 树和森林难度:259. 哈希查找算法与其他查找方法对比有何特点？何谓冲突？请写出两种解决冲突方法的名称。题型:简答题知识点:9.3 哈希表难度:160.设一个有序表为1，3，9，12，32，41，62，75，77，82，100，当采用折半查找值为80的结点时，几次比较后查找结束？请给出具体查找过程。题型:计算题知识点:9.1 静态查找表难度:261. 阅读如下算法，给出该算法的功能。void Unknown(Queue &Q) InitStack(S);while(!QueueEmpty(Q) i=

19、Dequeue(Q);Push(S,i);while(!StackEmpty(S) i=Pop(S);Enqueue(Q,i);题型:简答题知识点: 3 栈和队列难度:362.下面算法的功能是：在带头结点并且设立尾指针L的单向循环链表中第i个位置之前插入新的数据元素e。请在空缺处填入相应的语句。 Status ListInsert(LinkList &L, int i, ElemType e)LinkList p=L-next,s;int j=0;if(iListLength(L)+1) return ERROR;while (jdata=e;(2)_; (3)_; if( (4)_) (5)

20、_; return OK;题型:算法题知识点:2.3 线性表的链式表示和实现难度:263. 计算机算法必须具有输入、输出和( )这五个特征。A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性答案:B题型:单选题知识点:1.4 算法和算法分析难度:164. 数据的( )包括集合、线性结构、树形结构和图状结构四种基本类型。A. 逻辑结构和存储结构B. 存储结构C. 逻辑结构D. 物理结构答案:C题型:单选题知识点:1.2 基本概念和术语难度:165. 数据的最小单位是( )。A. 数据项B. 数据元素C. 数据结构D. 文件题型:

21、单选题知识点:1.2 基本概念和术语难度:166. 对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。A. 条件判断B. 元素移动C. 算术表达式D. 赋值语句题型:单选题知识点:2.2 线性表的顺序表示和实现难度:167. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用( )存储方式最节省时间。A. 顺序表B. 单链表C. 双链表D. 单循环链表题型:单选题知识点:2 线性表难度:368. 线性表中的链式存储结构是通过( )来表示元素之间的关系。A. 后继元素地址B. 元素的存储顺序C. 左、右孩子地址D. 后继元素的数组下标题型:单选题知识点:

22、2.3 线性表的链式表示和实现难度:169. 设p指向双链表的某一结点，则双链表结构的对称性可以用( )式来刻画。A. p-next-next= =p-prior-prior;B. p-prior-prior= =p-next-prior;C. p-prior-next= =p-next-next; D. p-prior-next= =p-next-prior;题型:单选题知识点:2.3 线性表的链式表示和实现难度:270. ( )不是队列的基本运算。A. 判断一个队列是否为空B. 从队头删除一个元素C. 在队列第i个元素之后插入一个元素D. 读取队头元素的值题型:单选题知识点:3.4 队列难

23、度:271. 在顺序栈中删除元素时，是( )。A. 先删除元素，再移动栈顶指针B. 先移动栈顶指针，再删除元素 C. 不分先后，同时进行D. 谁先谁后都可以题型:单选题知识点:3.1 栈难度:272. 常对数组进行的两种基本操作是( )。A. 查找和插入B. 插入和修改C. 建立和删除D. 查找和修改题型:单选题知识点: 5.1 数组的定义难度:273. 已知某二叉树的先序遍历为A，B，D，C，E，则它可能的中序遍历序列为( )。A. B，C，A，D，EB. C，B，A，D，EC. B，D，A，E，CD. B，E，A，C，D题型:单选题知识点:6.3 遍历二叉树和线索二叉树难度:274. 下面

24、关于图的存储的叙述中，( )是正确的。A. 用邻接矩阵法存储图，占用的存储空间数与图中结点个数有关，与边数无关B. 用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关C. 用邻接表存储图，占用的存储空间数与图中结点个数有关，与边数无关D. 用邻接表存储图，占用的存储空间数与图中边数有关，与结点个数无关 题型:单选题知识点:7.2 图的存储结构难度:275. 从逻辑结构来看，线性结构的特点是_。答案: 一对一题型:填空题知识点:1.2 基本概念和术语难度:176. 线性表的顺序存储结构称为_。答案: 顺序表题型:填空题知识点:2.2 线性表的顺序表示和实现难度:177. 在单链表

25、中，头结点的作用是_。题型:填空题知识点:2.3 线性表的链式表示和实现难度:278. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。题型:填空题知识点:2.3 线性表的链式表示和实现难度:279. 栈又称为_的线性表。题型:填空题知识点:3.1 栈难度:180. 循环队列Q为空队列的条件是_。题型:填空题知识点:3.4 队列难度:281. 广义表(a)的表尾是_。题型:填空题知识点:5.4 广义表的定义难度:182. 若一个具有N个顶点，K条边的无向图是一个森林(NK)，则森林有_棵树。题型:填空题知识点:6.1 树的定义和基本术语难度:383.

26、设无向图G的顶点数为n，则G最少有_条边。题型:填空题知识点:7.1 图的定义和术语难度:284. 若有向图中有n个结点，e条边，则它的邻接表需要_个表结点。题型:填空题知识点:7.2 图的存储结构难度:285. 对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的有序序列。题型:填空题知识点:9.2 动态查找表难度:186. 第一趟排序后序列中关键字最大的纪录交换到最后的排序方法是_。题型:填空题知识点:10 内部排序难度:287. 请用C语言给出循环队列(队列的顺序存储结构)的类型定义。答案:typedef struct QElemType *base;int front;int rea

27、r;SqQueue;题型:简答题知识点:3.4 队列难度:188. 在栈的输入端有5个元素，顺序为a,b,c,d,e。能否在栈的输出端得到序列cbdae和dcabe？若能，请给出栈操作的过程，若不能，简述其理由。题型:计算题知识点:3.1 栈难度:289. 用3，6，7，8，30作为叶子结点的值生成一棵赫夫曼树，并计算该树的带权路径长度。题型:计算题知识点:6.6 赫夫曼树及其应用难度:190. 对于n个顶点的无向图G，采用邻接矩阵A表示，如何判断下列问题：a图中有多少边？b任意两个顶点i和j是否有边相连？c任意一个顶点的度是多少？题型:简答题知识点:7.2 图的存储结构难度:291. 设哈希

28、表表长为11，哈希函数（用除留余数法）H(key) = key mod 11，解决冲突的方法为开放定址法Hi(key)=(H(key)+di)mod11，对下列关键字序列19，13，33，02，16，24，7，给出计算过程并构造哈希表。答案:H(19)=19mod11=8 H(13)=13mod11=2 H(33)=33mod11=0H(02)=02mod11=2 冲突 H1(02)=(H(02)+d1)mod11=(2+1)mod11=3H(16)=16mod11=5H(24)=24mod11=2冲突 H1(24)=(H(24)+d1)mod11=(2+1)mod11=3冲突 H2(24)=

29、(H(24)+d2)mod11=(2+2)mod11=4H(7)=7mod11=70123456789103313022416719题型:计算题知识点:9.3 哈希表难度:292. 试写出下面算法的功能。 Linklist Unknown (Linklist L) if (L & L-next) q = L;L = L-next;p = L;while (p-next) p = p-next; p-next = q; q-next = NULL; return L;题型:算法题知识点:2.3 线性表的链式表示和实现难度:393. 下面是起泡算法。请在空缺处填入相应的语句。 void Bubbl

30、esort(int A,int n)int j, i, sorted;i = sorted = 0;while (1)_) sorted = 1;for(2)_;ji; j-) if(3)_) temp = Aj; Aj = Aj-1; Aj-1 = temp;(4)_;(5)_;题型:算法题知识点:10.3 快速排序难度:294. ( )中任何两个结点之间没有逻辑关系。A. 树形结构B. 线性结构C. 图结构D. 集合答案:D题型:单选题知识点:1.2 基本概念和术语难度:195. 在以下的叙述中，正确的是( )。A. 线性表的线性存储结构优于链式存储结构B. 数据元素是数据的最小单位C.

31、二维数组是它的每个数据元素为一个线性表的线性表 D. 数据项是数据的基本单位答案:C题型:单选题知识点:1 绪论难度:296. 线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 A. 后继元素地址B. 元素的存储顺序 C. 左、右孩子地址D. 后继元素的数组下标题型:单选题知识点:2.2 线性表的顺序表示和实现难度:197. 设非空单循环链表的头结点为head，p所指结点为最后结点，则p应满足( )。A. p-next=NULLB. p=NULLC. p=headD. p-next=head题型:单选题知识点:2.3 线性表的链式表示和实现难度:298. 在顺序栈S中删除元素e时

32、，执行( )。A. S.top+; e = *S.top;B. S.top-; e = *S.top;C. e = *S.top; S.top+;D. e = *S.top; S.top-;题型:单选题知识点:3.1 栈难度:299. 链栈与顺序栈相比，有一个比较明显的优点，即( )。A. 插入操作更方便B. 删除操作更方便 C. 通常不会出现栈满的现象D. 通常不会出现栈空的现象题型:单选题知识点:3.1 栈难度:2100. 若顺序存储的循环队列的MAXQSIZE=n，则该队列最多可存储( )个元素。A. nB. n-1C. n +1D. 不确定题型:单选题知识点:3.4 队列难度:2101

33、. 广义表(a), (b)的表尾是( )。A. ( )B. bC. (b)D. (b)题型:单选题知识点:5.4 广义表的定义难度:1102. 稀疏矩阵一般的压缩存储方法有两种，即( )。A. 二维数组和三维数组B. 三元组表和散列表C. 三元组表和十字链表D. 散列表和十字链表题型:单选题知识点:5.3 矩阵的压缩存储难度:1103. A，B两个结点可以构成( )棵不等价的二叉树。A. 2B. 3C. 4D. 5题型:单选题知识点:6.2 二叉树难度:2104. 若无向图中有n个结点，e条边，则它的邻接表需要( )个表结点。A. nB. 2nC. eD. 2e题型:单选题知识点:7.2 图的

34、存储结构难度:2105. 快速排序方法在( )情况下最不利于发挥其长处。A. 被排序的数据量太大B. 被排序数据中含有多个相同值C. 被排序数据已基本有序D. 被排序数据数目为奇数题型:单选题知识点:10.3 快速排序难度:1106. 在图形结构中，每个结点的前驱结点和后继结点可以有_。答案: 任意个 或者 多个题型:填空题知识点:1.2 基本概念和术语难度:1107. 在顺序表中插入或者删除一个元素，平均需要移动_元素。答案: 一半题型:填空题知识点:2.2 线性表的顺序表示和实现难度:1108. 实现递归调用属于_的应用。题型:填空题知识点:3.2 栈的应用举例难度:2109. 在队列中，

35、可进行插入操作的一端称为_。题型:填空题知识点:3.4 队列难度:1 110. 若由4，6，8，10，12作为叶子结点的值生成一棵赫夫曼树，则该树的带权路径长度为_。题型:填空题知识点:6.6 赫夫曼树及其应用难度:2111. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为_。题型:填空题知识点:6.1 树的定义和基本术语难度:2112. 已知一个有向图的邻接矩阵表示，则删除所有从第i个结点出发的边的方法是_。题型:填空题知识点:7.2 图的存储结构难度:2113. Kruskal算法适用于边数较_的图。题型:填空题知识点:7.4 图的连通性问题难度:11

36、14. 设一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当采用折半查找值为95的结点时，_次比较后查找结束。题型:填空题知识点:9.1 静态查找表难度:2115. 在直接选择排序、起泡排序、直接插入排序方法中，不稳定的是_。题型:填空题知识点:10 内部排序难度:2116. 具有20个记录的序列，采用起泡排序最少的比较次数为_。题型:填空题知识点:10.3 快速排序难度:2117. 在待排序数据已基本有序的情况下，最佳的排序方法是_。题型:填空题知识点:10 内部排序难度:2118. 请用C语言给出单链表(线性表的链式存储结构)的类型定义。题型:简答题知

37、识点:2.3 线性表的链式表示和实现难度:1119. 设有多项式A(x) = 1 + 3x + 2x4，试用线性链表表示。题型:计算题知识点:2.4 一元多项式的表示及相加难度:2120. 用一维数组存放的一棵完全二叉树如下：ABCDEFGHIJK。请画出这棵完全二叉树，并写出后序遍历该二叉树的访问结点序列。题型:计算题知识点:6 树和二叉树难度:2121. 根据Prim算法构造下图的最小生成树。V11V2V3V4V5V6V742543823645题型:计算题知识点:7.4 图的连通性问题难度:2122. 以关键字序列12，2，16，9，10，8，20为例，分别写出执行以下排序算法的各趟排序结

38、束时，关键字序列的状态。(1) 冒泡排序 (2) 快速排序上述方法中，哪个是稳定的排序？哪个是不稳定的排序？题型:计算题知识点:10 内部排序难度:2123. 试写出下面无头结点线性表操作算法的功能。 NodeType Unknown(NodeType *h) p=NULL; q=h;while (q!=NULL) r=q-next;q-next=p;p=q;q=r;return (p);题型:算法题知识点:2.3 线性表的链式表示和实现难度:3124. 下面算法的功能是：在双向循环链表p所指结点之后插入s所指结点，所插入的元素为e。 Status ListInsert_Dul(DuLinkL

39、ist &L, ElemType e) if(!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR;s-data = e;(1)_; (2)_;(3)_; (4)_; return OK;题型:算法题知识点:2.3 线性表的链式表示和实现难度:2125. 数据的存储结构包括顺序、链式、索引和( )四种基本类型。A. 向量B. 数组C. 散列D. 集合答案:C题型:单选题知识点1.2 基本概念和术语难度:1126. 在算法的分析中，我们主要考虑算法的( )。A. 空间复杂性B. 易读性C. 时间复杂性D. 可行性答案:C题型:单选题知识点:1.4

40、 算法和算法分析难度1127. 下列数据结构中( )是线性数据结构。A. 二叉树B. 队列C. 赫夫曼树D. 无向图题型:单选题知识点:1.2 基本概念和术语难度:2128. 采用链式存储结构存储线性表的优点是( )。A. 便于随机存取B. 便于插入和删除操作C. 花费的存储空间比顺序存储少D. 数据元素的物理顺序与逻辑顺序相同题型:单选题知识点:2 线性表难度:2129. 在单链表中，头指针的作用是( )。A. 方便运算的实现B. 用于标识单链表C. 使单链表中至少有一个结点D. 用于标识首结点的位置。题型:单选题知识点:2.3 线性表队的链式表示和实现难度:2130. 在顺序栈中插入元素时

41、，是( )。A. 先存入元素，再移动栈顶指针B. 先移动栈顶指针，再存入元素C. 不分先后，同时进行D. 谁先谁后都可以题型:单选题知识点:3.1 栈难度:2131. 广义表(a)的表尾是( )。A. aB. (a)C. ( )D. (a)题型:单选题知识点:5.4 广义表的定义难度:1132. 在二叉树的先序遍历序列、中序遍历序列、后序遍历序列中，所有叶子结点的先后顺序( )。A. 都不相同B. 完全相同C. 先序和中序相同，而与后序不同D. 中序和后序相同，而与先序不同题型:单选题知识点:6.3 遍历二叉树和线索二叉树难度:2133. 赫夫曼树的带权路径长度是( )。A. 所有叶结点带权路

42、径长度之和B. 所有结点权值之和C. 带权结点的值D. 除根以外所有结点权值之和题型:单选题知识点:6.6 赫夫曼树及其应用难度:1134. 连通图的生成树是( )。A. 连通子图B. 顶点间可以无路径C. 边数为顶点数D. 极小连通子图题型:单选题知识点:7.4 图的连通性问题难度:1135. 对以下关键字序列用快速排序法进行排序，( )速度最慢。A. 18,24,5,13,9,22,31B. 24,22,31,13,18,5,9C. 5,9,13,18,22,24,31D. 18,9,13,31,24,22,5题型:单选题知识点:10.3 快速排序难度:1136. 若要从3000个元素中得

43、到20个最小值元素，最好采用( )方法。A. 直接插入排序B. 简单选择排序C. 起泡排序D. 快速排序题型:单选题知识点:10 内部排序难度:2137. 如一个结构中的数据中的数据元素之间存在一个对多个的关系，则称此结构为_。答案: 树形结构题型:填空题知识点:1.2 基本概念和术语难度:1138. 在表达式求值算法中，需要用_个栈。答案:2题型:填空题知识点:3.2 栈的应用举例难度:1139. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。题型:填空题知识点:2.3 线性表的链式表示和实现难度:2140. 设有一个顺序栈S，元素a,b,c,d,e,f依次入栈

44、，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为_。题型:填空题知识点:3.1 栈难度:2141. 设有循环队列Q，已知MAXQSIZE=18，Q.front=12，Q.rear=14，在连续执行了3次入队，2次出队，3次入队操作之后，(Q.front, Q.rear)的值为_。题型:填空题知识点:3.4. 队列难度:3142. 数组的逻辑结构是_的推广。题型:填空题知识点:5.1 数组的定义难度:1143. 二叉树中，度数为1的结点数等于m，度数为2的结点数等于n，那么度数为0的结点数等于_。题型:填空题知识点:6.2 二叉树难度:2144. 已知一个有向图的邻接矩阵表

45、示，则计算第i个结点的入度的方法是_。题型:填空题知识点:7.2 图的存储结构难度:2145. 若有向图中有n个结点，e条边，则它的邻接表需要_个头结点。答案:n知识点:7.2 图的存储结构难度:1146. 一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为_。题型:填空题知识点: 6.2 二叉树难度:2147. 请用C语言给出单链队列(队列的链式存储结构)的类型定义。答案:typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr front;Queu

46、ePtr rear;LinkQueue;题型:简答题知识点:3.4 队列难度:1148. 求图的最小生成树有哪些算法，各适用于什么情况？题型:简答题知识点:7.4 图的连通性问题难度:1149. 按中序序列遍历二叉树的结果为123，请画出满足此条件的所有不同形态的二叉树。题型:计算题知识点:6.3 遍历二叉树和线索二叉树难度:2150. 阅读如下算法，给出该算法的功能，并给出算法执行结束后，链表L的示意图。void Unknown(LinkList &L, int n) L=（LinkList）malloc(sizeof (LNode);L-next=NULL; s=L; for (i = n

47、; i0;-i) p = (LinkList)malloc(sizeof(LNode); p-data=i; s-next = p; s = p; s-next = NULL;题型:算法题知识点:2.3 线性表的链式表示和实现难度:3151.下面算法的功能是：在双向循环链表p所指结点之前插入s所指结点，所插入的元素为e。 Status ListInsert_Dul(DuLinkList &L, ElemType e) if(!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR;s-data = e;(1)_; (2)_; (3)_; (4)_;

48、 return OK;题型:算法题知识点: 2.3 线性表的链式表示和实现难度:2152. 一个队列的入列序列是1,2,3,4，则队列的输出序列是( )。A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,1答案:B题型:单选题知识点:3.4队列难度:1152. 在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是( )。A. 直接插入排序B. 快速排序C. 冒泡排序D. 简单选择排序题型:单选题知识点:10内部排序难度:2153. 有100个结点的树有_条边。题型:填空题知识点: 6.1 树的定义和基本术语难度:1154. 有字符串序列为“3*-ya/y”，试

49、利用栈将字符串次序改为“3y-*ay/”，请写出操作步骤。(可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的操作。例如：ABC变为BCA，则操作步骤为XXSXSS)。答案:XSXXXSSSXSXXSS 题型:简答题知识点: 3.1 栈难度:2155. 按行序为主序列出三维数组A232的所有元素在内存中的存储次序。题型:简答题知识点: 5.2 数组的顺序表现和实现难度:2156.下面算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素。请在空缺处填入相应的语句。void A(LinkList &La, SqList Lb) La

50、=(LinkList)malloc(sizeof (LNode);La-next=NULL;(1) _;for (i=0; idata=Lb.elemi; (2) _ ; (3) _; (4) _ ;题型:算法题知识点:2.3 线性表的链式表示和实现难度:2157. 广义表是数据元素的有限序列，其元素可以是单个元素，也可以是_。答案: 广义表题型:填空题知识点: 5.4 广义表的定义难度:1158. 遍历是指按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问_。题型:填空题知识点: 6.3 遍历二叉树和线索二叉树难度:1159. 下面算法的功能是：将一个带头结点并且头指针为A的单链表分解成两个单链表，其中分别含有原链表中序号为奇数和偶数的元素且保持原来的相对顺序。请在空缺处填入相应的语句。void Decompose(LinkList A) p = A-next;B =（LinkList）malloc(sizeof (LNode); r = B; while(p!=NULL & p-next!= NULL)q = p-next;p-next=q-next;(1)_; (2)_