《数据结构(本)试题D(08年7月已考)》由会员分享，可在线阅读，更多相关《数据结构(本)试题D(08年7月已考)（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构（本）试题 D 第 1 页（共 8 页） 数据结构2008 年 3 月一、单项选择题（每小题一、单项选择题（每小题 2 分，共分，共 30 分）分）1非空的单向循环链表的尾结点满足（ ） （设头指针为 head，指针 p 指向尾结点） 。Ap-next = =NULL Bp= =NULL Cp-next= =head Dp= =head 2一种逻辑结构（ ） 。A可以有不同的存储结构 B只能有唯一的存储结构 C是指某一种数据元素之间的存储关系 D以上三种说法均不正确 3把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ） 。A物理结构 B逻辑结构 C算法的具体实现 D给相关变
2、量分配存储单元 4在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（ ） 。Ap-next= s; s-next= p-next Bp-next=s-next; Cp=s-next Ds-next=p-next; p-next=s; 5在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（ ） 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s; 6元素 1，3，5，7 按顺序依次进栈，则该栈的不可能输出序列是（ ） （进栈出栈可 以交替进行） 。A7，5，3，1 B1，3，5
3、，7 C7，5，1，3 D3，1，7，5 7设有一个 20 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组 B 中（数组下标从 1 开始） ，则矩阵中元素 a9,2在一维数组 B 中的下标是（ ） 。 A41 B32 C18 D38 8设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（ ） 。A连接 B求子串 C求串长 D模式匹配 9在一棵二叉树中，若编号为 i 的结点存在左孩子，则左孩子的顺序编号为（ ） 。A2i B2i-1 C2i+1 D2i+2 10设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为 2，则该树共有（ ）个结点
4、。 A2n B2n+1 C2n+2 D2n-1题号一二三四总分分数得分评卷人数据结构（本）试题 D 第 2 页（共 8 页） 11已知如图 1 所示的一个图，若从顶点 a 出发，按深度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ） 。Aabecdf Bacfebd Caebcfd Daedfcb 图 1 12线性表以（ ）方式存储，能进行折半查找。A关键字有序的顺序 B顺序 C链接 D二插树 13有一个长度为 12 的有序表，按折半查找对该表进行查找，在等概率情况下查找成 功的平均比较次数为（ ） 。 A35/12 B39/12 C41/12 D37/12 14设已有 m 个元素有序，
5、在未排好序的序列中挑选第 m+1 个元素，并且只经过一次元 素的交换就使第 m+1 个元素排序到位，该方法是（ ） 。A折半排序 B冒泡排序 C归并排序 D简单选择排序 15一组记录的关键字序列为（47，80，57，39，41，46） ，利用堆排序（堆顶元素是 最小元素）的方法建立的初始堆为（ ） 。A39，41，46，80，47，57 B39，47，46，80，41，57 C41，39，46，47，57，80 D39，80，46，47，41，57二、填空题（每小题二、填空题（每小题 2 分，共分，共 24 分）分）1结构中的数据元素存在一对多的关系称为_结构。 2求两个 n 阶矩阵的乘积，算
6、法的基本操作和时间复杂度分别为_和 _。 3在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可 以用操作_ _。 4向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行_ _和 h=s; 操作。(结点的指针域为 next) 5串的两种最基本的存储方式分别是_ _ _和 _ _。 6对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 _、_和_ _三项信息。 7设有一棵深度为 4 的完全二叉树，第四层上有 5 个结点，该树共有_个结点。 （根所在结点为第 1 层） 8一棵二叉树中有 2n-2 条边（结点间的连线） ，其中每一个非叶结点的
7、度数都为 2， 则该树共有_个非叶结点。得分评卷人bdfeca数据结构（本）试题 D 第 3 页（共 8 页） 9如图 2 所示的二叉树，其中序遍历序列为_ _。图 210哈希函数是记录关键字值与该记录_ _之间所构造的对应关系。 11在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第 7 个记录 65 插入到有序表时，为寻找插入位置需比较_次。 12n 个元素进行冒泡法排序，通常需要进行_ _趟冒泡，第 j 趟冒泡要进行_ _次元素间的比较。三、综合题（每小题三、综合题（每小题 1010 分，共分，共 3030 分）分）1设查找表为(7,15,21
8、,22,40,58,68,80,88,89,120) ,元素的下标依次为 1,2,3,，11.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素 40 需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？得 分评卷人efg ibachd数据结构（本）试题 D 第 4 页（共 8 页） 2 （1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二 叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。（2）设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集
9、合中各数 据，构造一棵二叉排序树。3(1)以 2，3，4，7，8，9 作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点 的哈夫曼编码。 (2) 一棵哈夫曼树有 n 个叶结点，它一共有多少个结点？简述理由？数据结构（本）试题 D 第 5 页（共 8 页） 四、程序填空题（每空四、程序填空题（每空 2 2 分，共分，共 1616 分）分）1设线性表为（6，10，16，4） ，以下程序用说明结构变量的方法建立单向链表，并输 出链表中各结点中的数据。#define NULL 0void main( )NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.da
10、ta=16; d.data=4; /*d 是尾结点*/ head= （1） ; a.next= b.next= c.next=（2） ; /*以上结束建表过程*/ p=head; /*p 为工作指针，准备输出链表*/ doprintf(“%dn”, （3） );（4） ;while( （5） ); 2以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点） 。 void Inorder (struct BTreeNode *BT) if(BT!=NULL)（1） ;（2） ;Inorde
11、r(BT-right); 得分评卷人efabcd数据结构（本）试题 D 第 6 页（共 8 页） 利用上述程序对右图进行遍历，结果是 （3） ;图 3答案及评分标准（供参考） 一、单项选择题（每小题一、单项选择题（每小题 2 分，共分，共 30 分）分） 1C 2A 3A 4D 5B 6C 7D 8D 9A 10D 11D 12A 13D 14D 15A 二、填空题（每小题二、填空题（每小题 2 分，共分，共 24 分）分） 1树形 2乘法，O(n3) 3q-next=p-next; 4s-next=h; 5顺序存储 链式存储 6行下标、列下标、非零元素值 712 8n-1 9dgbaechi
12、f 10存储地址 113 12n-1,n-j三、综合题（每小题三、综合题（每小题 1010 分，共分，共 3030 分）分） 1 (1)图 4(2)4 次 (3)ASL=(1+2*2+3*4+4*4)/11=34711852101396数据结构（本）试题 D 第 7 页（共 8 页） 2(1)不正确，例图 5(2)图 63(1)图 715423955928141017240732997589243331518数据结构（本）试题 D 第 8 页（共 8 页） 2：0000 30001 4001 710 811 901 （2）2n-1 个，因为非叶结点数比叶结点数少一个。四、程序填空题（每空四、程序填空题（每空 2 2 分，共分，共 1616 分）分） 1 （1）&a （2）d-next=NULL （3）p-data （4）p=p-next （5）p!=NULL2 （1）Inorder(BT-left) （2） printf(“%c”,BT-data) （3）dbeafc
