数据结构95952

1、一、单项选择题，请在每小题的四个备选答案中选择一个，将其前面的字母填入（ ）中， 多选不得分。（每小题分，共分） 已知线性表L（ a ,a ,a ），下列说法正确的是（ ）。 1 2 n A 每个元素都有一个直接前趋和一个直接后继。 B 线性表中至少要有一个元素。 C 表中元素必须由小到大或由大到小排列。 D 除第一个和最后一个元素外，其余元素都有一个直接前趋和一个直接后继。 若某线性表最常用的操作是取第 i 个元素，则采用（ ）存储方式最节省运算时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 设栈S和队列Q的初始状态为空，元素e ,e , e ,e , e ,e ,依次通过栈S进

2、入队列Q，即一个元1 2 3 4 5 6 素出栈后即进入队列Q，若个元素的出队序列是e , e ,e , e ,e , e ，则栈S的容量至少 2 4 3 6 5 1 应该是（ ）。 A B C D 稀疏矩阵一般的压缩存储方法有（ ）两种。 A二维数组和三维数组 B三元组表和哈希表 C三元组表和十字链表 D哈希表和十字链表 5. 中序遍历一颗二叉排序树所得到的结点访问序列是结点值的（ ）序列。 A 递增或递减 B 递减 C 递增 D 无序 一棵深度为的满二叉树中节点总数为（ ）。 A B C D 一个单链表中，已知*q 结点是*p 结点的前趋结点，若在*q 和*p 之间插入*s 结点， 则必须

3、执行（ ）操作。 Aqnext=p next; p next=s; Bqnext=s; snext= p ; Cp next=snext; snext=p Dp next=s; snext=q 在顺序表2、5、7、10、14、15、18中，用二分法查找关键码 12需做（ ）次关键码 比较。 A2 B3 C1 D5 9. 一个具有 n 个顶点 e 条边的图中，所有顶点的度数之和等于（ ）。 An B2n C e D2e 10.若一棵完全二叉树中某结点无左孩子，则该结点一定是（ ）。 A度为的结点 B度为的结点 C叶子结点 D分支结点 数据结构试题 B (2002) 一、单项选择题，请在每小题的四

4、个备选答案中选择一个，将其前面的字母填入（ ）中， 多选不得分。（每小题分，共分） 数据结构研究（ ）。 A) 数据的逻辑结构B) 数据的物理结构C) 数据的逻辑结构与存储结构 D) 数据的逻辑结构、存储结构及操作的实现。 带头结点的单循环链表head 为空的判定条件是（ ） A ）head=NULL B）head->next=NULL C）head->next=head D)head=head 在双向链表存储结构中，在结点 p 后插入一个新结点 q，其操作为（ ）。 A）P->next=q; q->prior=p; p->next->prior=q; q-

5、>next=q; B）P->next=q; p->next->prior=q; q->prior=p;q->next=p->next; C）q->prior=p;q->next=p->next; p->next->prior=q; p->next=q; D）P->next=p->next; q->prior=p;p-next=q; q->next=p; 若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树 是( )。 A ） 二叉排序树 B ） 哈夫曼树 C ） 堆

6、D ）B树 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列 A) 前序 B) 中序 C) 后序 D) 按层序 在树中，若结点A 有四个兄弟，而且B 是A 的双亲，则B 的度为（ ）。 A） B） C） D） n 个顶点的连通图至少有（A ）条边 （A ） n-1 （B ） n （C） n+1 （D ）0 .设顺序表为4, 6, 12, 38, 40, 67, 80用二分法查找 72，需要进行的比较次数为（ ）。 A） B） C） D） 设数据结构为（D，R），其中D=a,b,c,d,e,f,R=<d,b>,<b,a>,<b,c>,<

7、d,f>,<f,e>，该数据 结构是（ ）。 A）线性表 B）有向图 C）无向图 D）树 10假设以S 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列 可表示为仅由 S 和O 组成的序列，称可以操作的序列为合法序列，否则为不合法序列。下 面的操作序列中，（ ）为不合法序列。 A）SOSSOSOO B）SOOSOSSO C）SSSOOSOO D）SOSOSO 数据结构试题 A(计算机 031-4, 网络 031-2, 软件 031-2) 一、单项选择题, 每小题后面有四个可供选择的答案,请从中选择一个正确的答案, 将其前 面的字母填写在( )中。(共

8、20 分,每小题 2 分) 1. 用链表表示线性表的优点是 ( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 2.有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100, 如果采用二分查找法, 查 值为 82 的结点时，（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 3.一棵二叉树有 67 个结点，这些结点的度或者是 0，或者是 2。这棵二叉树中度为 2 的结 点有( )个。 A. 33 B.34 C.32 D.30 4.队列与一般线性表的区别在于( )。 A. 数据元素的类型不

9、同 B. 插入或删除操作的位置受限制 C. 数据元素的个数不同 D. 逻辑结构不同 5.在一个单链表中，已知 q 所指节点是 p 所指节点的前驱节点，若在 q 和 p 之间插入 s 节 点，则执行( )。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s;s->next=q; 6. 设进栈的顺序为 a b c d，则不可能得到的出栈序列是( )。 A.a b c d B.d c b a C.a c d

10、 b D.d a b c 7.将下列查找算法, 按查找速度从慢到快的顺序排列, 正确的是（ ）。 A.顺序 折半 哈希 分块 B.顺序 分块 折半 哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半 8.具有 n 个顶点的有向完全图有（ ）条弧。 A.n B.n*(n-1) C.n*(n+1) D.n*n 9.一棵深度为 5 的满二叉树中,结点的总数为 ( )。 A.31 B.32 C.33 D.16 10. 二维数组A910 采用行优先的存储方法，若每个元素占 3个存储单元且A00 的地址为200，则A69 的地址为( )。 数据结构试题 B(计算机 031-4 网络 031-2

11、软件 031-2) 一、单项选择题, 每小题后面有四个可供选择的答案,请从中选择一个正确的答案, 将其前 面的字母填写在( )中。(共 20 分,每小题 2 分) 在一个具有n个结点的有序单链表中，若插入一个新结点，单链表仍然有序，则算法的 时间复杂度为（ ）。 O(1) O(n) O(n2) O(nlog2n) 下列数据结构中，（ ）是线性结构。 A树 B 队列 C图 D A 和B 设单链表中指针p 指向结点a，若要删除a 之后的结点（若存在），则需要修改指针的 操作为（ ）。 Ap->next=p->next->next p=p->next Cp= p->ne

12、xt->next p->next=p 若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是( ) 9 B11 C12 D、不确定 下列四棵二叉树中（ ）是一个堆。 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。 A 上三角矩阵 B 稀疏矩阵 C对角矩阵 D. 对称矩阵 二叉树第i(i>=1)层上至多有（ ）结点。 i i Ai i n 个顶点的连通图至少有（ ）条边。 An-1 Bn Cn+1 D 0 采用折半查找方法进行查找，数据文件应为（ ）。 有序表 顺序存储结构 B 有序表 链式存储结构 C 随机表 顺序存储结构

13、D 随机表 链式存储结构 10从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需平 均比较（ ）个结点。 n n/2 （n-1 ）/2 (n+1)/2 一、单项选择题, 每小题后面有四个可供选择的答案,请从中选择一个正确的答案, 将其前面的字母填写在( ) 中。(共 10 分,每小题 2 分) 1. 数据结构中, ( )是线性结构。 A. Graphics B. Tree C. Generalized list D. Queue 2. 树型结构中元素间存在( ）的关系。 A. 一对一 B. 多对多 C. 一对多 D. 随机 3. ( )是下面的有向图的拓扑有序序列。

14、 A. A、C、B、D、E、F B. A、B、C、D、E、F C. A、B、D、C、E、F D. F、E、D、B、C、A 4. 在有 n 个叶子结点的哈夫曼树中结点总数为( ）。 A. 不确定 B. 2n-1 C. 2n D. 2n+1 5.稀疏矩阵一般的压缩存储方法有( )两种。 A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表 二、问答题:（共分，每小题 5 分） 1. 什么是数据结构? 数据结构主要研究哪三个方面的问题? 2. 如果一棵树有n 个度为 1 的结点, 有n 个度为2 的结点, 有n 个度为3 的结点, 则该树有多少个度为0 的结点?

15、 1 2 3写出推导步骤。 三、应用题:(共 40 分,每小题 10 分) 1. 有一组数据（20，69，15，32，8，6，88，65，12，19），请分别用 SHELL 排序法（第一趟排序的增量为， 第二趟增量为 3）和选择排序法对其按由小到大的次序排序，写出第一趟和第二趟的排序结果。 一、单项选择题, 每小题后面有四个可供选择的答案,请从中选择一个正确的答案, 将其前面的字母填写在( ) 中。(共 10 分,每小题 2 分) 1. 数据的( )结构,包括集合、线性表、树和图结构 4 种基本类型。 A.存储结构 B.逻辑结构 C.基本运算 D.算法描述 2. 数据的存储结构包括顺序;链接;

16、散列和( )4 种基本类型。 A. Vector B. Array C. Sets D. Index 3. 设栈的输入序列是 1 2 3 4,则( )是不可能的出栈序列。 A.1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 4. 一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。 A. 250 B. 500 C. 254 D.501 5.假定有 K 个关键字互为同义词,若用线性探测法把这 K 个关键字存入散列表中,至少要进行( )次探测。 A.K-1 次 B. K(K-1)/2 次 C.K+1 次 D.K(K+1)/2 次 二、问答题:（共分，每小

17、题 5 分） 1. 什么是栈，栈的特点有哪些？ 2. 如果二叉树中度为 2 的结点个数为 n2,则叶子结点的个数 n0 为多少? 要求有计算步骤。 三、应用题:(共 40 分,每小题 10 分) 1. 有一组数据（34，16，5，7，8，100，23，19，27，13），请分别用堆排序法和冒泡排序法对其按由大到小 的次序排序，写出第一趟和第二趟的排序结果。 一单项选择题（每题2分，共20分）1顺序表是线性表的 （ ）链式存储结构 顺序存储结构 索引存储结构 散列存储结构2.对于顺序表的优缺点，以下说法错误的是 （ ） 无需为表示结点间的逻辑关系而增加额外的存储空间 可以方便地随机存取表中的任一

18、结点 插人和删除运算较方便 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)3. 单链表中，增加头结点的目的是为了 ( )使单链表至少有一个结点 标示表结点中首结点的位置方便运算的实现 说明单链表是线性表的链式存储实现4.循环队列的队满条件为（在牺牲一个存储空间的情况下） ( )rear % maxsize =(front+1) % maxsize;(rear+1)% maxsize = front+1(rear+1)% maxsize = frontrear = front5.循环队列的人队操作应为 ( )rear= rear+1 datarear=xdatarear=x re

19、ar= rear+1rear=( rear+1)% maxsize datarear=xdatarear=x rear=(rear+1)% maxsize6设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是 （ ） 0 1 2 3 maxsize-1a1a2a3sq top a3,a1,a4,a2 a3,a2,a4,a1 a3,a4,a2,a1 a4,a3,a2,a17以下说法错误的是 ( ) 二叉树可以是空集二叉树的任一结点都有两棵子树二叉树与树具有相同的树形结构二叉树中任一结点的两棵子树有次序之分8深度为5的二叉树最多有( )个结点(设树的层

20、数为6) 64 63 32 319将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( )图142 40 21 2010在图1的二叉树中，（ ）不是完全二叉树。二填空题（1-3题每空2分，4-6题每空1分，共20分）1下面程序段的时间复杂度T(n)= _。for(i=l;i<=n;i+)k+;for(j=1;j<=n;j+)l+=k;2以下运算实现在顺序栈上的进栈，请在_处用适当的以填充（存放栈元素的数组为ElmList）。template<class ELEM>void Push(ELEM

21、item) if(top >= maxsize-1cerr << “栈满” << endl;return;_= item ; _； 3. 以下运算实现在循环队上的出队列，请在_处用适当句子予以填充。（存放队列元素的数组为ElmList）图2template<class ELEM> ELEM Queue:DeQueue() if(curr_len = = _)cerr << “队空” << endl;return； ELEM temp = _; _ _ ; return temp; 4.二叉树第i(i>=0)层上至多有_个结

22、点。5.对任何二叉树，若度为2的节点数为n2，则叶子数n0=_。6一棵树的形状如图2所示，它的根结点是_，叶子结点是_ _，这棵树的度是_，这棵树的深度是_，结点F的孩子结点是_，结点G的父结点是_。三问答题（每题10分，共40分）1数据结构研究的内容有哪些，数据结构的逻辑结构有哪些，存储结构有哪些？2画出图3所示二叉树的中序线索二叉链表存储结构示意图。图3AJIFCHGDB3已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。4给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树，并求这棵哈夫曼树的带权路径长度WPL。四算法设计

23、题（每题10分，共20分）1 设A=（a1,a2,a3,.an）和B=(b1,b2,. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,. .,n),则称A=B;若ai=bi(i=1,. .,j)且aj+1<bj+1（j<n<=m）, 则称A<B;在其他情况下均称A>B。试编写一个比较A和B的算法，当A<B,A=B或A>B是分别输出-1，0或者1。2假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。五选作题（任选其一，共10分）1设有线性表A=(a1,

24、a2,. .,am)和B=(b1,b2,. .,bn).试写合并A、B为线性表C的算法，使得：C=假设A、B均以单链表为存储结构。2有一二叉链表，按后根遍历时输出的结点顺序为a1, a2,an-1, an。试编写一算法，要求输出后根序列的逆序an,an-1 ，a2 , a1 。一 单项选择题（每题2分，共20分）1.以下数据结构中，（ ）是非线性数据结构A.图 B.字符串 C.队 D.栈2.队列的特点是（ ）。 A.先进先出 B. 后进先出 C.没有约束 D. 先进后出 3.有个元素6,5,4,3,2,1顺序进栈，问下列哪一个是不合法的出栈序列：A.5,4,3,6,1,2  

25、;   B.4,5,3,1,2,6     C.3,4,6,5,2,1     D.2,3,4,1,5,64.设顺序表的长为n,则其每个元素(查找概率均等)的平均查找长度是 （ ）A.n B. (n-1)/2 C. n/2 D. (n+1)/25.下面关于串的叙述中，哪一个是不正确的（ ）A.串是字符的有限序列 B.空串是由空格构成的串C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储6某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G

26、、E，则其左子树中结点数目为（ ）A.3 B.2 C.4 D.57.如果一个图有e条边，则图中所有顶点的度的和是（ ）。A.e B. e/2 C. 2e D. e-18.下面关于图的存储的叙述中正确的是（ ）A.邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关；B.邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关；C.邻接表占用的存储空间只与图中结点个数有关，而与边数无关；D.邻接表占用的存储空间只与图中边数有关，而与结点个数无关。9.下面的排序算法中，时间复杂度不是O(n2）的是（ ）。 A.直接插入排序 B.冒泡排序 C.二路归并排序 D.直接选择排序10.已知广义表LS=

27、(a,(b,c),(d,e,f)，该广义表的长度为（ ）。 A.3 B.6 C.1 D.2二问答题（每题10分，共40分）1. 画出与下图所示的二叉树相对应的森林，并写出该森林的先序和后序遍历序列。ABCDEFGH2. 对于下面的图，请完成下列任务:(1)画出它的邻接表 (2)写出从顶点A出发的深度优先搜索序列 (3)求从A到其他顶点的最小路径。391081261519 6ABDFEC3.判别序列（12，70，33，65，24，56，48，92，86，33）是否为小顶堆，如果不是，则把它调整为小顶堆， 写出小顶堆所对应的序列。4. 已知散列函数为H(K)=K mod 13,关键码序列为25，3

28、7，52，43，84，99，120，15，26，11，70，82，1，采用拉链法处理冲突，画出构造的开散列表，并计算查找成功的平均查找长度。三算法阅读题（要求：写出算法功能，并举例说明）（每题5分，共15分）1. struct Node char data; Node *llink; Node *rlink; ;void function1 (Node* root) f(root!=NULL) function1(root->llink); cout << root->data << “ “; function1(root->rlink); 2. vo

29、id function2(char A, int n)char x;int s, h, m;for(int i=1;i<n;i+)x = Ai; s = 0; h = i - 1;while(s<=h)m = (s+h)/2;if(x < Am) h = m- 1;else s = m + 1;for(int j=i-1;j>=s;j-) Aj+1 = Aj;As = x;3. int function3( char *d, char *s)int i =0; while (si != '0' && di != '0' )

30、 if (di > si) return 1; else if (di < si) return -1; i +; if( di = ='0' && si != '0') return -1; else if (si = = '0'&& di != '0') return 1; return 0; 四算法设计题（第一题10分，第二题15分）1 已知一个整数顺序表L，要求将其拆分为一个正整数顺序表L1和一个负整数顺序表L2。2无向图采用邻接表方式存储，要求编写按广度优先搜索策略实现对图的遍

31、历算法。一、单选题, 从可供选择的4个答案中, 选择一个正确的答案, 将其前面的字母填写在( )中,共40分,每小题4分。1.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。A.s->next=p->next;  p->next=s;   B.q->next=s;   s->next=p; C.p->next=s->next;  s->next=p;   D.p->next=s;   s->

32、next=q;2.带头结点的单链表为空的判定条件是( )。A.head= =NULLB.head->next= =NULLC.head->next= =head  D.head!=NULL3. 若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。A度为的结点 B度为的结点 C叶子结点 D分支结点4.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙5在长度为n的线性表中查找值为x的数据元素的时间复杂度为： （ ）。A. O(0) B. O(1) C. O(n) D. O(n2)6一个栈的入栈序

33、列是a, b, c, d, e，则栈的不可能的出栈序列是（ ）。A. edcba B. cdeba C.debca D.abcde7前序遍历和中序遍历结果相同的二叉树是（ ）。A. 根结点无左孩子的二叉树 B. 根结点无右孩子的二叉树C. 所有结点只有左子树的二叉树 D. 所有结点只有右子树的二叉树8.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A1 An中，结点Ai若有左子树，则左子树的根结点是（ ）。 A. A2i-1 B.A2i+1 C.Ai/2 D.A2i9.对任何一棵四叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，度为3的结点个数为n3,度为4的结点个数为n4

34、,则（ ）。 A.n0=n2+n3+n4+1 B.n0=n2+2n3+3n4+1 C.n0=n1+n2+2n3+3n4+1 D.没有规律10.算法指的是（ ）。A. 对特定问题求解步骤的一种描述 B. 计算机程序 C. 解决问题的计算方法 D. 数据处理二、填空题, 请将答案填写在题目的( )内。（共24分，每小题6分）1在一个长度为n的顺序表的第i（1in+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1in）个元素时，需向前移动（ ）个元素。2. 权值为2, 4, 1,7, 3，5的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。3. 已知一棵二叉树的前序遍历序列为ABC

35、DEFGH，中序遍历序列为CDBAFEHG，该二叉树的后序遍历序列是4. 已知二叉链表的结点结构 lchild data rchild其中，data：数据域，存储元素的值lchild：左指针域，存储左孩子指针rchild：右指针域，存储右孩子指针请将Struct BiNode的定义填写完整。template <class T>struct BiNode ; ; ; ;三、阅读下列算法, 将合适的语句填写在_处, 使算法完善。(共24分,每小题6分)1.在线性表中查找元素x, 若找到x, 返回第一个找到的x的序号, 若找不到,返回0const int MaxSize =100; te

36、mplate  < class T >/模板类 SeqList class SeqListpublic private:       T dataMaxSize; / 存放数据元素的数组       int length; / 线性表的长度 ; template <class T> SeqList<T>:Locate(T x)/在线性表中查找元素x，返回其在表中的序号 for (int i=0; i<length; i+) if return

37、i+1; /下标为i的元素等于x，返回其序号i+1 ; /退出循环，说明查找失败2. 算法的功能是将一个十进制整数转换为二至九进制之间的任一进制数(用r表示)输出。void Decimaltor(int num, int r) top=-1;/采用顺序栈, 并假设栈不会溢出 While (num!=0) ; S+top=k; ;While (top!=-1) ;3. 循环顺序队列入队操作const int QueueSize=100;template <class T> class CirQueuepublic:void EnQueue(T x); private: T dataQ

38、ueueSize; /存放队列元素的数组 int front, rear; ; template <class T> void CirQueue<T>:EnQueue(T x) /元素x入队列 if throw "队列已满" ; ; /在队尾处插入元素4. 按中序遍历次序输出二叉树中的叶子结点的值template <class T>struct BiNode /二叉树的结点结构 T data; BiNode<T> *lchild, *rchild;template <class T>class BiTreepublic: BiTree( ); /构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiTree(void); /析构函数，释放二叉链表中各结点的存储空间private: BiNode<T> *root; /指向根结点的头指针 ;template<class T>void BiTree<T>:leaf(BiNode<T> *root) if(root=NULL) return;else ; if ;