模拟试题6

模拟试题6

一、选择题（每小题1分，共10分）

1、如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为R={,,,< D, C >,< G, E>,< G, F >},则该数据结构是一种 。

(A)线性结构 (B)树结构 (C)图结构 (D)链表结构

2、设有二维数组A[50][60]，其元素长度为1个字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为 。

(A)820 (B)720 (C)1210 (D)1410

3、一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为 。

(A)5 (B)6 (C)7 (D)8

4、具有20个结点的二叉树，其深度最多为 。

(A)4 (B)5 (C)6 (D)20

5、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为 。

(A)front==rear (B)（rear+1）%MAXSIZE==front (C)front-rear==1 (D)rear%MAXSIZE==front

6、一个5×5的对称矩阵采用压缩存储，需要存储 个元素。

(A)5 (B)10 (C)15 (D)20

7、一个无向连通图有5个顶点、8条边，则其生成树将要去掉 条边。

(A)3 (B)4 (C)5 (D)6 8、设一颗二叉树共有50个叶子结点（终端结点），则共有 个度为2的结点。

(A)25 (B)49 (C)50 (D)51 二、填空题（每题2分，共16分）

1、一个算法，如果不管问题规模大小，运行所需时间都是一样，则该算法的时间复杂度是 。

2、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是 。

3、在求最小生成树的两种算法中， 算法适合稀疏图。

4、一棵哈夫曼树是由5个叶子结点形成的，该哈夫曼树总共有 个结点。 5、设循环队列Q[1….N]的头尾指针分别为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素个数为 。 6、一个具有5个结点的有向图最少有 条弧。

7、二叉排序树采用 序遍历可以得到结点的有序序列。 8、设有1000个元素，用二分法查找时，最大比较次数是 。 三、判断题（每题1分，共8分，对的打√，错的打×）

1、如果某数据结构的每一个元素都最多只有一个直接后继结点，则必为线性表。（ ） 2、如果某有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。（ ） 3、如果把一个大顶堆看成一棵二叉树，根元素层次为1，则层次越大的元素值越小。（ ） 4、Huffman树没有度为1的结点。（ ）

5、在冒泡排序中，关键字的比较次数与记录的初始排列无关。（ ）

1

6、设一棵二叉树共有50个叶子结点（终端结点），则它共有49个度为1的结点。（ ） 7、一个有序的单链表采用折半查找法比采用顺序查找法效率要高得多。（ ） 8、一个图可以没有边，但不能没有顶点。（ ） 四、简答题（共38分） 1、排序。

（1）写出线性表（26，45，12，2.，30，6，15，29，16，2，18）采用基数排序后，第一趟结束时的结果。（4分）

（2）采用简单选择排序算法对线性表（26，15，12，16，5，30）进行排序，进行交换的第一对元素是哪两个元素?在什么情况下，第一趟不需进行元素的交换？（6分） 2、已知二叉树如图1所示。

A（1）给出该二叉树的后序遍历的结果。（5分）

BC（2）如果图1表示的是采用孩子——兄弟法

转换后的一棵树，请画出原来的树。（5分）

DEF

G?1

3、已知图2是一个有向图

BC（1）画出该有向图的邻接矩阵。（5分）

E（2）基于你给出的邻接矩阵，求从顶点B出发的深度

DF优先遍历。（5分）

A ?2

4、已知有序表（4，11，13，19，26，28，33，39，42），采用折半查找 （1）各元素的平均查找长度是多少？（4分）

（2）查找值为10的元素，查找时与哪几个元素进行了比较？（4分） 五、程序填空题（共15分）

1、已知STACK表示栈的数据结构，push是将一个值为e的元素进栈，成功返回1，否则返回0。完成以下程序。（4分） typedef struct {

int data[100];

int top;/*栈顶元素的下标*/ } STACK;

int push(STACK *S,int e) {

if( ) {

return 0; }

++S->top;

2

=e; return 1; } 2、以下程序是在二叉排序树T中找出值最大的元素，并返回其地址，如果空树则返回NULL，完成程序。（6分） Typedef struct linkNode {

int data;

struct linkNode *lchild,*rchild; } Node;

Node *sm(Node *T) {

Node *p;

if( ) {

return NULL; }

for(p=T; p!=NULL: p=p->rchild);

return; }

3、写出以下程序的输出结果。（本题5分） int strc(char s[],char t[]) {

int i;

for(i=0;s[i]!=0&&t[i]!=0; ++i) {

if(s[i] != t[i])

{

break;

}

return(s[i]-t[i]); } }

void main() {

printf(\ }

六、编程题（共15分）

3

1、编写算法对一个整型数组中的元素进行位置调整，将所有负数放在下标较低的一端，将所有正数放在下标较高的一端，所有的0在中间。（8分）

2、编写算法，在一棵二叉树中查找值为x的叶子结点，找到返回该结点的指针，找不到返回空指针。（7分）

已知二叉树结点数据结构如下： Typedef struct linkNode {

int data;

struct linkNode *lchild,*rchild; } Node;

4

模拟题6答案

一、选择题 1 B 2 A 3 B 4 D 5 A 6 C 7 B 8 B 二、填空题 1、O(1) 2、O(n2) 3、Kruskal 4、9 5、（R-F+N）%N 6、4 7、中 8、10

三、判断题 1 × 2 × 3 √ 4 √ 5 × 6 × 7 × 18

6

8 √ 2

四、简答题 1、（1）45 30 26 20 29 12 16 （2）交换的第一对元素为26 15，第一个元素比其他元素都小 2、（1）D B G E F C A （2） AC

F

BEG D 3、（1） A B C D E F

A 0 0 0 0 1 1 B 0 0 0 0 1 0 C 0 0 0 0 0 1 D 1 1 0 0 0 0 E 0 0 1 1 0 0 F 0 0 0 0 0 0 （2）B E C F D A 4、（1）（1*20+2*21+3*22+4*（9-20-21-22））/9=25/9 （2）26 11 4 五、程序填空题 1、（1）top>=100 或者 top==99

5

本文来源：https://www.bwwdw.com/article/ljph.html