最新1111 数据结构试题1.doc

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

1、精品资料1111 数据结构试题1.数据结构试题 1 时间：120分钟 满分：100分 一、 选择题(每小题1分，共20分)1以下数据结构中， A 是线性结构。A）队 B）树 C二叉树 D）图25个顶点的无向图最多有 B 条边。A、5 B、10 C、20 D、253下面 C 是顺序存储结构的优点。A）存储密度大 B）插入运算方便 C查找方便 D）适合各种逻辑结构的存储表示4下面关于串的叙述中， 是不正确的。A）串是字符的有限序列 B）空串是由空格构成的串C）模式匹配是串的一种重要运算 D）串既可以采用顺序存储，也可以采用链式存储5 B 的邻接矩阵是对称矩阵。A）有向图 B）无向图 C）AOV网

2、D）AOE网6用链式方式存储的队列，在进行删除运算时， A 。A）仅修改头指针 B）仅修改尾指针 C）头、尾指针都要修改 D）头、尾指针可能都要修改 7二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是 G 。先序序列：EFHIGJK 中序序列：HFIEJKGA）E B）F C）G D）H8下面 B 方法可以判断出一个有向图中是否有环。A）深度优先遍历B）拓朴排序C）求最短路径D）求关键路径9 若在线性表中采用折半查找法查找元素，该线性表应该 C 。A）元素按值有序 B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构 D）元素按值有序，且采用链式存储结构10从未排序序列中依次取出一

3、个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。A）插入 B）选择 C）冒泡 D）都不是11在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）插入一个新元素时，需要从后向前依次后移 C 个元素。 A、n-i B、n-i-1 C、n-i+1 D、i12一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是 。A、edcbaB、decba C、dceabD、abcde13从邻接矩阵可以看出，该图共有 B 顶点。A、9 B、3 C、6 D、114上题中，若是有向图，则有 B 条弧。A、5 B、4 C、3 D、215n个节点的完

4、全二叉树，编号为i的节点是叶子结点的条件是 D 。A、inB、2*inD、2*in16向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素。A、64.5B、64C、63D、6517在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 D 。A、q-next=p-next; p-next=q; B、p-next=q-next; q=p;C、p-next=p-next; q-next=q; D、p-next=q-next; q-nxet=p;18对一个满二叉树，m个树叶，n个结点，深度为h，则有 D 。A、n=h+mB、h+m=2nC

5、、m=h-1D、n=2-119假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为 A 。A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL20在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 A 。A、选择排序B、冒泡排序 C、插入排序D、希尔排序二、判断题：（判断下列各题正误，正确的在题目后面的括号内写“对”，错误的在题目后面的括号内写“错”。每小题2分，共10分）（ ）1. 栈和队列都是非线性数据结构。 （ ）2. 完全二叉树可以用顺序存储结构进行存储。（ ）3. 数据元素是数据的最小单位。(基本单

6、位)（ ）4. 含尾指针的单链循环表可以被用于队列操作。（ ）5. 数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。三、填空题（每空2分，共10分）1、 在线性表的单链表存储结构中，每个结点包含两个域，一个叫 数据（值） 域，另一个叫 指针 域 。2、 设字符串S1=ABCDEFG，S2=PQRST，则运算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值为 BCDEF EF 。3、 队列的插入操作在 队尾 进行，栈的删除操作在 栈顶 进行。四、回答下列问题（每小题8分，共40分）1 分别给出对下图进行深度优先和广度优先遍历的结果

7、。1324786591深度：125963784 （不唯一） 广度：123456789 （不唯一）2已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。2第1趟：4 12 17 10 7 30 第2趟：4 7 17 10 12 30第3趟：4 7 10 17 12 30第4趟：4 7 10 12 17 30第5趟：4 7 10 12 17 303一批数据有如下的逻辑结构B=(K ,R),其中K=, R=r, r= ,试用图示法表示其逻辑结构。1 234875694已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI 后序：

8、GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。 前序遍历结果:ACBGDEHFJI5已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。 c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:00五、编写算法（每小题10分，共20分）要求: 1、说明算法中使用的主要数据结构、变量；2、用C可1设有一个由正整数组成的无序无头结点的单链表，编写子程序(或函数)找到其最小值。struc node int d; struct node *next; int minn(node *p) int x=0; while(p) if(p-dd; p=p-next; RETURN(x); 2冒泡排序。 int n; int pn; void sort(int p,n) int i,j,t,k; for (i=0; in-1 & k; i+) k=1; for(j=0;j+;jpj+1) t=pj; pj=pj+1; pj+1=t; k=0;