数据结构(本)试题d(08年7月已考)

《数据结构(本)试题d(08年7月已考)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构2008年3月题号一二三四总分分数得分评卷人一、单项选择题（每小题2分，共30分）1．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。A．p->next==NULLB．p==NULLC．p->next==headD．p==head2．一种逻辑结构（）。A．可以有不同的存储结构B．只能有唯一的存储结构C．是指某一种数据元素之间的存储关系D．以上三种说法均不正确3．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。A．物理结构B．逻辑结构C．算法的具体实现D．给相

2、关变量分配存储单元4．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。A．p->next=s;s->next=p->nextB．p->next=s->next;C．p=s->nextD．s->next=p->next;p->next=s;5．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（）。A．f->next=s;f=s;B．r->next=s;r=s;C．s->next=r;r=s;D．s->next=f;f=s;6．元素1，3，5，7按顺序依次进栈，则该栈的不可

3、能输出序列是（）（进栈出栈可以交替进行）。A．7，5，3，1B．1，3，5，7C．7，5，1，3D．3，1，7，57．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A．41B．32C．18D．388．设有两个串p和q，求q在p中首次出现的位置的运算称作（）。A．连接B．求子串C．求串长D．模式匹配9．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。A．2iB．2i-1C．

4、2i+1D．2i+210．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个结点。A．2nB．2n+1C．2n+2D．2n-111数据结构（本）试题D第8页（共8页）．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfB．acfebdC．aebcfdD．aedfcbbdfeca图112．线性表以（）方式存储，能进行折半查找。A．关键字有序的顺序B．顺序C．链接D．二插树13．有一个长度为12的有序表，按折半查找对该表进行

5、查找，在等概率情况下查找成功的平均比较次数为（）。A．35/12B．39/12C．41/12D．37/1214．设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（）。A．折半排序B．冒泡排序C．归并排序D．简单选择排序15．一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。A．39，41，46，80，47，57B．39，47，46，80，41，57C．41，39，46，

6、47，57，80D．39，80，46，47，41，57得分评卷人二、填空题（每小题2分，共24分）1．结构中的数据元素存在一对多的关系称为________结构。2．求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为________和________。3．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作________。4．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行________和h=s;操作。(结点的指针域为next)5．串的两种最基本的存储方式分别是___

7、____和________。6．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_______、_______和_______三项信息。7．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_______个结点。（根所在结点为第1层）8．一棵二叉树中有2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有_______个非叶结点。9．如图2所示的二叉树，其中序遍历序列为_________。数据结构（本）试题D第8页（共8页）efgibachd图210．哈希函数是记

8、录关键字值与该记录______之间所构造的对应关系。11．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_________次。12．n个元素进行冒泡法排序，通常需要进行________趟冒泡，第j趟冒泡要进行______次元素间的比较。得分评卷人三、综合题（每小题10分，共30分）1．设查找表为(7,15,21,22,