数据结构习题求数据结构期末测试题一套

数据结构习题  时间:2021-01-09  阅读:()

数据结构判断题

您好!数据结构习题 一、选择题 1.数据结构中,与所使用的计算机无关的是数据的( )。

A.存储结构 B.物理结构 C.逻辑结构 D.物理和存储结构 2.下面有关数据的存储结构的叙述中,正确的是( )。

A.顺序存储方式只能用于存储线性结构 B.顺序存储方式的优点是存储密度大,且插入和删除运算效率高 C.链表的每一个结点都恰好包含一个指针 D.栈和队列的存储方式既可以顺序存储,也可以采用链式存储方式 3.下列叙述中正确的是( )。

A.线性表是线性结构 B.栈与队列是非线性结构 C.线性链表是非线性结构 D.队列是后进先出的线性表 4.链表不具有的特点是( )。

A.可随机访问任一元素 B.插入和删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表长度成正比 5.栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是( )。

A.ABCED B.DBCEA C.CDABE D.DCBEA 6.若进栈序列为1,2,3,4,则( )不可能是出栈序列。

A.1,2,3,4 B.4,3,2,1 C.3,4,2,1 D.2,4,3,1 7.在深度为8的满二叉树中,叶子结点的个数为( ) A.63 B.64 C.127 D.128 *8.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( )。

A.cedba B. acbed C. decab D.deabc 9. 设有下列二叉树: 对此二叉树中序遍历的结果为___ A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 10. 下列关于栈的叙述中正确的是____ A)在栈中只能插入数据 B)在栈中只能删除数据 C)栈是先进先出的线性表 D)栈是先进后出的线性表 11. 下列关于队列的叙述中正确的是___ A)在队列中只能插入数据 B)在队列中只能删除数据 C)队列是先进先出的线性表 D) 队列是先进后出的线性表 12. 对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为___ A)N+1 B)N C)(N +1)/2 D)N/2 13. 在计算机中,算法是指___ A)查询方法 B)加工方法 C)解题方案的准确而完整的描叙 D)排序方法 二、填空题 1.栈的基本运算有三种:入栈、退栈和【 】。

2.对长度为N的线性表进行顺序查找,当查找失败时比较次数为【 】。

3.在长度为N的线性表中进行二分查找,在最快的情况下,需要比较的次数为【 】。

4.设待排数据元素的关键字为(67,24,14,22,33,15,11,15),用选择法将其按升序排序,需要比较的次数为【 】。

5.某二叉树中度为2的结点有12个,则该二叉树中有 【 】个叶子结点。

6.设一棵二叉树中有3个叶子结点,有6个度为1的结点,则该二叉树中总的结点数为【 】 个。

*7.在深度为5的完全二叉树中,度为2的结点数最多为【 】个。

8.对下列二叉树进行前序、中序和后序遍历的结果分别是【 】 、【 】和 【 】 。

前序遍历 FCADBEG、中序遍历 ACBDFEG 后序遍历 ABDCGEF 9. 在深度为5的满二叉树中,叶子结点的个数为【 】一、选择题 1.C 2.D 解析:A.完全二叉树可以用数组存储,树是非线性结构 B.链表且插入和删除运算效率高 C.链表也有双向链表 ,有两个指针域 3.A 4.A.顺序表可随机访问任一元素 5.D 6.这道题你是不是弄错了 全都对啊 7.D 满二叉树 :结点总数目N=2^H -1 H为数高度 ,求出结点总数为255 满二叉树,只有度为0 和度为2 的结点,度为0 的结点等于度为1 结点数目+1 因此选D 8.C 这题不用画图就可做出来, 后序遍历序列是dabec,------》得到根节点是:c 前序遍历;根左右 所以第一个一定是c 只有A项符合 9. A 虽然你没给图 但是一般都是A相 因为见过好多这个题 中序遍历和层次遍历结果一样 10. D 11.C 12.B 在最坏情况:比较次数为___每次查找都要从第一个比较到最后一个,都要遍历N次 : 总的比较次数N*N,平均比较次数就是N 13. C 二、填空题 1.出栈 2.n/2+n/(n+1) 1+2+3……n+n)/(n+1)=.n/2+n/(n+1) 3.1 4.设待排数据元素的关键字为(67,24,14,22,33,15,11,15),用选择法将其按升序排序,需要比较的次数为【 】。

5.13 6.11 3+6+2=11 *7.15 方法 同选择题 上那个满二叉树 8.无图 9. 16 和第七题一样的方法

十万火急,,求助大家帮忙做《数据结构》试题!!!!

你在考电大的数据结构?哇哈哈 和我一样啊 ~~ 程序填空: 以下函数是二叉排序树的查找算法,若二叉树为空,则返回根结点的指针,否则,返回值是指向树结点的 结构指针p(查找成功p指向查到的树结点,不成功p指向为NULL)完成程序中的空格。

typedef struct Bnode { int key; struct Bnode *left; struct Bnode *right; }Bnode; Bnode *Bsearch(Bnode *bt,int k) /*bt用于接收二叉顺序树的根结点的指针,k用于接收要查找的关键字*/ { Bnode *p; if (bt==(1)________) return(bt); p=bt; while(p->key!=(2)________) { if(kkey) (3)_________; else(4)_________; if(p==NULL) break; } Return(5)________; } 以下函数为链队列的出队操作(链队列中带有头结点),出队结点的数据域的值由x返回,front、rear分 别是链队列的队头、队尾指针。

struct node { ElemType data; struct node *next; }; struct node *front,*rear; ElemType OutQueue() { ElemType x; if((1)________) { printf("队列下溢错误! "); exit(1); } else { struct node *p=front->next; x=p->data; front->next=(2)_________; if(p->next==NULL) rear=front; free(p); (3)________________; } }

数据结构考试,20题,只要及格就给分。

下面是这二十个的答案,保证你及格: 1-5 bddad 6-10 11-15 11222 16-20 12111 对第二题有疑问,因为b和d都是稳定的。

不过一题不影响

求数据结构高手 做几道题 悬赏两百分

三、 判断题(每小题1分,共10分,错误打×,正确打√) 1、线性的数据结构可以顺序存储,也可以链接存储。

非线性的数据结构只能链接存储。

.......................( ×) 2、单链表从任何一个结点出发,都能访问到所有结点........( ×) 3、在只有度为0和度为k的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1 ( ×) 4、将一棵树转换成二叉树后,根结点没有左子树( ×) 5、邻接表表示无向图,邻接表中的结点个数是无向图中边数的2倍。

(× ) 6、 用邻接矩阵表示图所用的存储空间大小与图的边数成正比。

(× ) 7、负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度。

( √) 8、赫夫曼树一定是满二叉树。

(× ) 9、高度为h的k叉树至多有kh-1 个结点。

(k^h-1 ) 10、对任意一个图,从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

( × ) 2、键码序列(26,25,20,33,21,24, 42,37),要用散列法进行存储,规定负载因子α=0.5。

1) (2分)请给出除余法的散列函数。

m=16,p<16的质数设p=13 hash(key)=key mod 13 2) (3分)用链接法解决碰撞,请画出插入所有的关键码后得到的散列表。

0 ——> 26 1 2 3——>42 4 5 6 7 ——>20——>33 8 ——>21 9 10 11——>24——>37 12 ——> 25 3、(6分)已知序列[10,18,4,3,6,12,l,9,15,8],请给出采用希尔排序法(d1=5、2、1)对该序列做升序排序时的每一趟的结果。



第一趟:10 1 4 3 6 12 18 15 8 第二趟: 4 1 6 3 8 12 10 15 18 第三趟: 1 3 4 6 8 10 12 15 18 7、(6分)下图表示一个地区的通讯网,边表示城市间的通讯线路,边上的权表示架设线路花费的代价,选择能沟通每个城市且总代价最省的n-1条线路,画出选择的过程和最终结果。

看不见图,这是一个最小生成树问题

寻一份《数据结构》试题及答案

《数据结构》试题

一、选择题(每小题2分,共30分)

1. 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素,则采用( )存储方式最节省时间。

A、单链表 B、双链表 C、单向循环 D、顺序表

2. 串是任意有限个( )

A、符号构成的序列 B、符号构成的集合

C、字符构成的序列 D、字符构成的集合

3. 设矩阵A(aij ,l≤i,j≤ 10)的元素满足:

aij≠0(i≥j, l≤i, j≤ 10)

aij=0 (i<j, l≤i, j≤ 10)

现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中,每个元素占有4个单元,则元素A[9][5]的首址为

A、2340 B、2336 C、2164 D、2160

4. 如果以链表作为栈的存储结构,则退栈操作时( )

A、 必须判别栈是否满

B、 对栈不作任何判别

C、 必须判别栈是否空

D、 判别栈元素的类型

5. 设数组Data[0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )

A、front=front+1 B、front=(front+1)% m

C、rear=(rear+1)%m D、front=(front+1)%(m+1)

6. 深度为6(根的层次为1)的二叉树至多有( )结点。

A、 64 B、32 C、31 D、63

7. 将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次对结点编号,根结点的编号为1。

编号为49的结点X的双亲编号为( )

A、24 B、25 C、23 D、无法确定

8. 设有一个无向图G=(V,E)和G’=(V’,E’)如果G’为G的生成树,则下面不正确的说法是( )

A、G’为G 的子图 B、G’为G 的边通分量

C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图

9. 用线性探测法查找闭散列表,可能要探测多个散列地址,这些位置上的键值( )

A、 一定都是同义词 B、一定都不是同义词

C、都相同 D、不一定都是同义词

10. 二分查找要求被查找的表是( )

A、 键值有序的链接表 B、链接表但键值不一定有序

C、 键值有序的顺序表 D、顺序表但键值不一定有序

11. 当初始序列已经按键值有序,用直接插入算法对其进行排序,需要循环的次数为( )

A、n2 B、nlog2n C、log2n D、n-1

12. 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )

A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2i

C、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n)

13.一个具有n个顶点的无向完全图的边数为(  )

A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)

14.在索引顺序表中查找一个元素,可用的且最快的方法是(  )

A、用顺序查找法确定元素所在块,再用顺序查找法在相应块中查找

B、用顺序查找法确定元素所在块,再用二分查找法在相应块中查找

C、用二分查找法确定元素所在块,再用顺序查找法在相应块中查找

D、用二分查找法确定元素所在块,再用二分查找法在相应块中查找

15.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用(  )存储方式最节省运算时间。

A、 单链表  B、双链表 

C、带头结点的双循环链表 D、容量足够大的顺序表

二、判断题(每小题1分,共10分)

1.双链表中至多只有一个结点的后继指针为空。

( )

2.在循环队列中,front指向队列中第一个元素的前一位置,rear指向实际的队尾元素,队列为满的条件是front=rear。

( )

3.对链表进行插入和删除操作时,不必移动结点。

( )

4.栈可以作为实现程序设计语言过程调用时的一种数据结构。

( )

5.在一个有向图的拓朴序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>。

( )i

6.对有向图G,如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点,则该图一定是完全图。

( )

7.“顺序查找法”是指在顺序表上进行查找的方法。

( )

8.向二叉排序树插入一个新结点时,新结点一定成为二叉排序树的一个叶子结点。

()

9.键值序列{A,C,D,E,F,E,F}是一个堆。

10.二路归并时,被归并的两个子序列中的关键字个数一定要相等。

()

三、填空题(每小题2分,共20分)

1.在带有头结点的单链表L中,若要删除第一个结点,则需执行下列三条语句:________;L->next=U->next;free(U);

2.有一个长度为20的有序表采用二分查找方法进行查找,共有______个元素的查找长度为3。

3.采用冒泡排序对有n个记录的表A按键值递增排序,若L的初始状态是按键值递增,则排序过程中记录的比较次数为_____。

若A的初始状态为递减排列,则记录的交换次数为_______。

4.在无头结点的双链表中,指针P所指结点是第一个结点的条件是______。

5.G为无向图,如果从G的某个顶点出发,进行一次广度优先搜索,即可访问图的每个顶点,则该图一定是_____图。

6.如果一个有向图中没有______,则该图的全部顶点可能排成一个拓扑序列。

7.深度为8(根的层次号为1)的满二叉树有______个叶子结点。

8.将一棵有100个结点的完全二叉树按层编号,则编号为49的结点X,其双亲PARENT(X)的编号为_______。

9.设某闭散列表HT未满,散列函数H(KEY)为键值第一字母在字母表中的序号,处理冲突方法为线性探测法,请在下列算法划线处填上适当内容,以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。

void printword(keytype HT[m])

{ for(i=1;i<=26;i++)

{ j=i;

while(____________________)

{ if (____________________) printf(“datatype”,HT[j]);

j=(j+1)% m;

}

}

}

10.设有一个链队,结点结构为data|next,front为队头指针,rear为队尾指针,当执行入队操作时需执行下列语句:

malloc(p);p->data=x; p->next=NULL;

________________;

________________;

四、简答题:(每小题4分,共20分)

1. 对于一个有10000个结点的二叉树,树叶最多有多少个?最少有多少个?

2. 已知一棵二叉树的中序序列和后序序列分别为: DBGEACHF和DGEBHFCA,则该二叉树的前序序列是什么?

3. 设有1000个无序的元素,需排出前10个最大(小)的元素,你认为采用哪种排序方法最快?为什么?

4. 在KMP算法中,已知模式串为ADABCADADA ,请写出模式串的next[j]函数值。

5. 中序遍历的递归算法平均空间复杂度为多少?

五、 算法设计题(每小题10分,共20分)

1. 试编写一个算法,判断一给定的整型数组a[n]是不是一个堆。

2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。

试写一高效算法,求二叉树的繁茂度。

参考答案

一、选择题

1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C

13、B  14、C  15、D  

二、判断题

1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. ×

三、填空题

1.U=L - > next

2.4。

 

3.n-1、n(n-1)/2。

4.p - > prior = NULL。

5.连通

6.回路或环

7.28-1 = 27 = 128

8.24

9.HT[j]!=NULL或HT[j]不为空、H(HT[j])=I

10.rear - > next = p、rear = p

四、简答题:

1. 答: 最多是完全二叉树的形态,即5000个叶子;最少是单支树的形态,即1个叶子。

2.答:是:ABDEGCFH

3. 答:用锦标赛排序或堆排序很合适,因为不必等全部元素排完就能得到所需结果,

时间效率为O(nlog2n); 即O(1000log21000)=O(10000)

锦标赛排序的准确比较次数为:n-1+9log2n=999+9log21000=999+9×10=1089

堆排序的准确比较次数为:n-1+9log2n=999+9log21000=999+9×10=1089

若用冒泡排序也较快,最多耗费比较次数为(n-1+n-2+……+n-10)=10n-55=10000-55=9945(次)

4. 答: 0112112343

5. 答: 要考虑递归时占用了栈空间,但递归次数最多不超过树的高度,所以空间复杂度为O(log2n)

五、 算法设计题

1.解:提示:堆的定义是:ki<k2i和K2i+1

void SortA(sqlist &A, int n)

{ if(n==0) return(0); //空表

if (a[1]<a[2])

{ for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);

return(minleap)

};

else

{ for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);

return(“maxleap”)

};

}

2. 要用层次遍历以及队列来处理,可以增设一个宽度计数器,在统计完每一层的结点个数之后,再从计数器中挑出最大值。

typedef struct {

BTNode node; int layer;

//layer是结点所在层数

} BTNRecord, r ;

int Width(Bitree T ){ //求树宽

int count[ ]; //增开count向量,存放各层对应的结点数

InitQueue(Q); //队列初始化,Q的元素为BTNRecord类型

EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0],下标值

while(!QueueEmpty(Q))

{ DeQueue(Q, r); //结点出队

count[r.layer]++; //出队时再把结点对应层的计数器加

if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1});

if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1});

} //按层序入队时要随时标注结点所在层号

h=r.layer; //最后一个队列元素所在层就是树的高度

for(maxn=count[0], i=1; h; i++)

if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多

return (h*

maxn)} // Width

求数据结构期末测试题一套

一、单选题 1. 以下数据结构中哪一个是线性结构?( ) A. 有向图 B. 栈 C. 线索二叉树 D. B树 2. 在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( )。

A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 3. 在一个带有头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( )。

A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 4. 单链表的每个结点中包括一个指针next,它指向该结点的后继结点。

现要将指针q指向的新结点插入到指针p指向的单链表结点之后,下面的操作序列中哪一个是正确的?( ) A.q=p->next; p->next=q->next; B.p->next=q->next;q=p->next C. q->next=p->next; p->next=q; D. P->next=q; q->next=p->next; 5. 在一个循环顺序存储的队列中,队首指针指向队首元素的( )位置。

A. 前一个 B. 后一个 C. 当前 6. 以下哪一个不是队列的基本运算?( ) A.从队尾插入一个新元素 B.从队列中删除第i个元素 C.判断一个队列是否为空 D.读取队头元素的值 7. 用链接方式存储的队列,在进行删除运算时( ). A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改 8. 对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 9. 字符A、B、C依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成( )个不同的字符串? A.5 B.4 C.6 D.1 10. 下述哪一条是顺序存储方式的优点?( ) A.存储密度大 B.插入运算方便 C. 删除运算方便 D.可方便地用于各种逻辑结构的存储表示 二、填空题 1. 数据的逻辑结构被分为_________、________、__________和___________四种。

2. 数据的物理结构被分为_________、________、__________和___________四种。

3. 一个算法的时间复杂度为(3n2+2nlog2 n+4n-7)/(5n),其数量级表示为________。

4. 对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。

5. 对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。

6. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为________和________。

7. 一个广义表中的元素分为________元素和________元素两类。

8. 从一个链栈中删除一个结点时,需要把栈顶结点的_________域的值赋给________。

9. 进行函数调用时,需要把每个实参的值和调用后的________传送给被调用的函数中。

10. 设W为一个二维数组,其每个数据元素占用6个字节,行下标i从0到8 ,列下标j从0到3 ,则二维数组W的数据元素共占用__个字节。

W中第6 行的元素和第4 列的元素共占用__个字节。

若按行顺序存放二维数组W,其起始地址为100,则二维数组W的最后一个数据元素的起始地址为__。

更多的在/b118506/d12173882.htm

虎跃云-物理机16H/32G/50M山东枣庄高防BGP服务器低至550元每月!

虎跃科技怎么样?虎跃科技(虎跃云)是一家成立于2017年的国内专业服务商,专业主营云服务器和独立服务器(物理机)高防机房有着高端华为T级清洗能力,目前产品地区有:山东,江苏,浙江等多地区云服务器和独立服务器,今天虎跃云给大家带来了优惠活动,为了更好的促销,枣庄高防BGP服务器最高配置16核32G仅需550元/月,有需要的小伙伴可以来看看哦!产品可以支持24H无条件退款(活动产品退款请以活动规则为准...

腾讯云轻量服务器老用户续费优惠和老用户复购活动

继阿里云服务商推出轻量服务器后,腾讯云这两年对于轻量服务器的推广力度还是比较大的。实际上对于我们大部分网友用户来说,轻量服务器对于我们网站和一般的业务来说是绝对够用的。反而有些时候轻量服务器的带宽比CVM云服务器够大,配置也够好,更有是价格也便宜,所以对于初期的网站业务来说轻量服务器是够用的。这几天UCLOUD优刻得香港服务器稳定性不佳,于是有网友也在考虑搬迁到腾讯云服务器商家,对于轻量服务器官方...

racknerd:美国大硬盘服务器,$599/月,Ryzen7-3700X/32G内存/120gSSD+192T hdd

racknerd当前对美国犹他州数据中心的大硬盘服务器(存储服务器)进行低价促销,价格跌破眼镜啊。提供AMD和Intel两个选择,默认32G内存,120G SSD系统盘,12个16T HDD做数据盘,接入1Gbps带宽,每个月默认给100T流量,5个IPv4... 官方网站:https://www.racknerd.com 加密数字货币、信用卡、PayPal、支付宝、银联(卡),可以付款! ...

数据结构习题为你推荐
金士顿内存卡价格金士顿的手机内存卡多少钱软银收购wework如何看待腾讯收购 Supercell涡轮增压和自然吸气哪个好本田车自然吸气和涡轮增压哪个好燃气热水器和电热水器哪个好电热水器和燃气热水器哪一个更安全,且更节省能源?免费阅读小说app哪个好有什么好用的看小说的app三国游戏哪个好玩三国系列的游戏哪个好玩?炒股软件哪个好炒股软件真的那么好用吗?炒股软件哪个好用玩股票哪个软件好?电陶炉和电磁炉哪个好电磁炉和电陶炉买哪个?电陶炉和电磁炉哪个好电陶炉和电磁炉哪个好
域名中介 域名系统 fc2新域名 韩国服务器租用 VPS之家 vps代购 国外免费域名网站 bandwagonhost godaddy主机 国外服务器 免费静态空间 免费网络电视 牛人与腾讯客服对话 html空间 浙江独立 刀片服务器的优势 ca187 atom处理器 发证机构 机柜尺寸 更多