《数据结构》模拟试题2
一、 单项选择题
1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。
A．单链表 B．双链表 C．顺序表 D．单循环链表 2．链表所具备的特点是（ ）。
A．可以随机访问任一结点 B．占用连续的存储空间
C．插入删除元素的操作不需要移动元素结点 D．可以通过下标对链表进行直接访问 3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A．物理 B．逻辑 C．存储 D．逻辑与物理
4．设有一个长度为n的顺序表，要在第i个元素之前插入一个元素（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。 A．n-i+1 B．n-i C．n-i-1 D．i
5．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（ ）。
A．p=q->next B．p->next=q C．q->next=NULL D．p->next=q->next
6．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的植，则执行（ ）。
A．x=top->data; top=top?next; B．x=top->data;
C．top=top->next; x=top->data; D．top=top->next; x=data;
7．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。 A．f->next=s; f=s; B．s->next=r;r=s; C．r->next=s;r=s; D．s->next=f;f=s; 8．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储
到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ ）。
A．18 B．45 C．53 D．58 9．一棵有n个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 A．n B．n+1 C．n-1 D．n-2 10．设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 A．n B．2n C．n-1 D．n+1
11．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 A．30 B．20 C．21 D．23
12．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到
的一种顶点序列为（ ）。
A．abecdf B．acfebd C．aedfcb D．aebcfd
a b e c d 图1
V1 f
V2 V3 V4 V5 V6 V7 V8 图3
13．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。
A．3 B．4 C．6 D．8
14．有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的
平均比较次数为（ ）。
A．37/12 B．39/12 C．41/12 D．35/12 15．一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键
字为分割元素，经过一次划分后结果为（ ）。
A．40，38，46，79，56，84 B．40，38，46，84，56，79 C．40，38，46，56，79，84 D．38，40，46，56，79，84
二、填空题
1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为______ __结构。 2．结构中的数据元素存在 的关系称为树形结构。
3．求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为________和____ ____。 4．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= = head，则p所指结点为 。
5．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作________,就可使该单向链表构造成单向循环链表。
6．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行 和h=h->next; (结点的指针域为next) 。
7．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为________。 (结点的指针域为next)
8．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。
9．一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个叶结点。
10．中序遍历二叉排序树可得到一个 。
11．如图1所示的二叉树，其先序遍历序列为_________。 12．如图2所示的二叉树，其前序遍历序列为_________。
13．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是______的。(回答正确或不正确)
三、综合题
1．设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程） （1）以二叉树描述6个元素的初始堆
（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆 2．一组记录的关键字序列为（46，79，56，38，40，84）
（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）
（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 3．设查找表为(16,15,20,53,64,7),
(1)用冒泡法对该表进行排序（要求升序排列），要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？
(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)
(3)求在等概率条件下,对上述有序表成功查找的平均查找长度. 4．
(1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树. （2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果. 5．
(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。
(2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？ 6．如图所示的二叉树
a （1）给出中序遍历序列
（2）给出先序遍历序列 （3）给出后序遍历序列
b c
d e f
g h i 四、程序填空题
1．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，要求按升序排列。 void bsort (NODE a[ ], int n) { NODE temp; int i,j,flag;
for(j=1; ;j++); {flag=0;
for(i=1; ;i++) if(a[i].key>a[i+1].key)
{flag=1; temp=a[i]; ; ; }
if(flag= =0)break; } }
程序中flag的功能是 ?
2．以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域从前向后依次为n,n-1,……,1，完成程序中空格部分。 NODE *create2(n) {NODE *head , *p, *q; int i;
p=(NODE*)malloc(sizeof(NODE)); p->next=NULL; head= ? ; ? ; for(i=1; i<=n; i++) { p= ? ; p->data=i; if(i= =1)
p->next=NULL; else
p->next= ? ; q->next= ? ; }
return(head); }
3．以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 void Preorder (struct BTreeNode *BT) { if(BT!=NULL){
? ;
相关推荐：
loading