2011datastructure习题

更新时间:2024-04-11 06:37:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

题1.1

数据结构在计算机内存中的表示是指———。 A.数据的存储结构 B.数据元素

C.数据的逻辑结构 D.数据元素之间的关系 题1.2

从逻辑上可把数据结构分为——。

A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性存储结构 D.内部结构和外部结构 题1.3

判断正误:数据元素是数据的最小单位。 题1.4

分析下列程序段的时间复杂度: (1) x=1;

for (i=1;i<=n;i++)

for (j=1;j<=i;j++)

for (k=1;k<=j;k++)

x++;

(2) for (i=1;i

for (j=0; j<=(2*n); j++)

x++;

}

(3) i=1; while (i<=n) i=i*2 (4) i=0; s=0; while(s

{ i=i+1; s=s+i; }

题1.5

设n是偶数,试计算运行下列程序段后m的地址并给出该程序段的时间复杂度。 m=0;

for(i=1;i<=n;i++) for(j=2*i;j<=n;j++) m=m+1;

题2.1

线性表的静态链表存储结构与顺序存储结构相比优点是——。 A.所有的操作算法实现简单 B.便于随机存取 C. 便了插入和删除 D.便于利用零散的存储器空间 题2.2 判断正误

? 1.顺序存储只能用于存储线性结构

? 2.顺序查找法适用于存储结构为线性或链接存储的线性表。

题2.3

若较频繁地对一个线性表进行插入和删除操作,该线性表宜用什么存储结构,为什么? 题2.4

? 线性链表中各链接点的位置——。 A.必须连续 B.部分地址必须连续 C. 不一定连续 D.连续与否无所谓

题2.5

? 线性表是具有n个( )的有限序列。

(1)表元素 (2)字符 (3)数据元素 (4)数据项 (5)信息项

题2.6

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个元素的时间复杂度为(1<= i <= n+1 )。

A.O(0) B.O(1) C.O(n) D.O(n2) 题2.7

? 表长为n的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个

元素需移动元素的平均个数 ,删除一个元素需移动元素的平均个

数 。

题2.8

? 已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->next=q,

q->prior=p),请写出删除q所指向结点的程序段。

题2.9

? 将两个各有n个元素的有序表归并成一个有序表,其最小的比较次数

是 。 A.n B.2n-1 C.2n D.n-1 题2.10

? 填空:在一个单链表的p结点之前插入一个人结点s时,可执行如下操作: (1)s->next = ; (2)p->next = s; (3)t = p->data;

(4)p->data = ; (5)s->data = ; 题2.11

? 带头结点的双向循环链表L为空表的条件是 。 题2.12

? 需要分配较大存储空间,插入和删除不需要移动元素的线性表,其存储结构

是 。 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 题2.13

? 有一个单链表L,其结点的元素值以非递减有序排列,编写算法删除该单链表中多

余的元素值相同的结点。

题2.14

? 有一个单链表L(至少有一个结点),其头结点指针为L,编写一个过程将L置逆,要

求逆转在原链表上进行

题3.1

若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列删除一个元素,再加入两个元素后,rear和front的值分别为 。 A.1和5 B.2和4 C.4和2 D.5和1

题3.2

? 用数组表示的循环队列的队首位置和队尾位置分别为1和max_size,试给出判断队

列为空和满的条件(队列长度最大为MAXSIZE)。 题3.3

若某堆栈的输入序列为1,2,3,…,n,输出序列的第一个元素为n,则第i个输出元素为 。

A.i B.n-i C. n-i+1 D.哪个元素无所谓 题3.4

设栈的输入序列是1,2,3,4,则 不可能是其出栈顺序。 A. 1243 B.2134 C.1432 D.4312 E.3214

题3.5

设输入元素为1、2、3、P和A,输入次序为123PA。元素经过栈后到达输出序列,当所有元素都到达输出序列后,有哪些序列可作为高级语言的变量名。

题3.6

设栈S和队列Q的初始状态为空,元素a、b、c、d、e、f依次通过栈S,一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a,则栈的容量至少为? 题3.7

用数组Q(其下标在0…n-1,共有n个元素)表示一个循环队列,f为当前对头元素的前一位置,r为队尾元素位置,假定队列中元素个数总小于n,求队列中元素个数的公式是 。

题4.1

? 是C语言中“abcd321ABCD”的子串。

A.abcd B.321AB C. “abcABC” D.“21AB”

题4.2

? 字符串满足为下式,其中Head和Tail的定义与广义表类似,则S= 。

? Contact(Head(Tail(S)), Head(Tail(Tail(S)))) = “dc”

? A. abcd B.acbd C.acdb D.adcb 题4.3

设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非空子串(不含S本身)的个数是 。

A.2n-1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E.(n2/2)+(n/2)+1

题4.4

? 若串S = “software”,其非空子串数目为( )。 A.8 B.37 C. 36 D.9

题4.5

? 填空:两个串相等的充分必要条件是 。 题4.6

? 空串和空格串的区别是?

题5.1

? 填空:设有上三角矩阵A(aij)n*n,将其上三角元素逐行存于数组B[1…m]中(m充分

大),使得B[k]=aij,则k= 。 题5.2

数组a中,每个元素a[i, j]的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址连续存放在存储器内,该数组按行优先存放时,元素a[7][4]的起始地址为 . A.a+141 B.a+144 C.a+222 D.a+225

题5.3

填空:已知10行20列的二维数组A按行优先方式存放,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[5][11]的地址是 ;如果该数组按列优先方式存放,则A[5][11]的地址是 。

题5.4

? 填空:有一个10阶对称矩阵A,采用压缩存储方式(以行序位主序且A[0][0]地址为

1),则A[7][4]的地址为 。 题5.5

? 填空:将一个A[0..99, 0..99]的三对角矩阵,按行优先存入一维数组B[0..297]中,A

中元素A[65][64]在B中的位置k为 。

题5.6

? 若广义表A满足Head(A) = Tail(A),则A为 。

? A.( ) B.(( )) C.(( ), ( )) D.(( ), ( ), ( ))

题5.7

? 设广义表L = (( ), ( )),则Head( L)= ,Tail( L)= ,L的长度

是 ,L的深度是 。 题6.1

? 设高度为h的二叉树上只有度为0和度为2的结点,则此二叉树中所包含的结点数

至少为 ,至多为 。

A.2h B.2h-1 C.2h+1 D.h+1

E.2h-1 F.2h-1 G.2h+1 H.2h+1+1 题6.2

? 某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出该二叉树,

并求其后序遍历序列。

题6.3

若一个具有n个顶点,k条边的无向图是一个森林(N>K),则该森林中必有 颗树。 A.k B.n C.n-k D. 1

题6.4

? 填空:深度为k的完全二叉树至少有 个结点, 至多有 个结点,k

和结点n的关系为 。

题6.5

? 填空:一棵有100个叶子结点的完全二叉树,最多有 结点。 题6.6

? 具有n个结点的满二叉树,其叶子结点有 个。

题6.7

? 已知某字符串S共有8种字符,各种字符分别出现2次、1次、4次、5次、7次、3

次、4次和9次,对该字符串用{0, 1}进行前缀编码,问该字符串的编码至少有多少

位。

题6.8

? 填空:有n个结点的二叉树,已知叶子结点个数为n0,写出求度为1的结点的个数

n1的计算公式 ;若二叉树中仅有度为0和度为2的结点,写出求该二叉树结点个数n的公式 。 题6.9

? 请编写一个函数(int LeafCount(Binary_tree BT) ),求此二叉树的叶子结点个数。有关的数据结构已描述如下: typedef struct { //二叉树结点 int data;

Binary_node *lchild; Binary_node *rchild; }Binary_node,*Binary_tree; 题6.10

? 已知某系统在通信联络中只可能出现八种字符(a,b,c,d,e,f,g,h),其概率

分别为5%, 29%, 7%, 8%, 14%, 23%, 3%, 11%,试设计对应Huffman树,根据此

Huffman树写出每个字母的赫夫曼编码。

题7.1

? 给出该图的邻接矩阵、邻接表、逆邻接表。

题7.2

设无向图的顶点个数为n,则该无向图最多有 条边。

A.n-1 B.n(n-1)/2 C.n(n+1)/2 D. n2 题7.3

? G是一个连通图,共有28条边,则该图至少有 个顶点,如果G是非连通的,

则该图至少有 个顶点。 ? A.6 B.7 C.8 D.9 题7.4

Kruskal算法的时间复杂度是 ,它对 图较为合适。

题7.5

? 用Prim算法(从顶点1出发)和Kruskal算法分别构造图G的最小生成树。 题7.6

对于如图所示的事件结点网络,求出各活动可能的最早开始时间和最晚完成时间,并问哪些活动是关键活动。

a1=4 12 a5=6 a2=3 a3=2 3 a4=4 4

题9.1

? 对长度为12的递增有序表(a1,a2,…,a12)进行折半查找,在设定查找不成功时,关

键字xa12以及ai不成功的平均查找长度是多少。

题9.2

? 若在线性表中采用折半查找法,该线性表应该( )。 ? A.元素按值有序 B.采用顺序存储结构 ? C.元素按值有序,且采用顺序存储结构

? D.元素按值有序,且采用链式存储结构

题9.3

已知序列17,31,13,11,20,35,25,8,4,24,40,27,请画出该序列的二叉排序树,并分别给出下列操作后的二叉树:1)插入数据9,2)删除结点17。

题9.4

含有12个结点的平衡二叉树的最大深度是 (设根结点深度为1)。 题9.5

? 在非空m阶B-树上,除根结点以外的所有其他非终端结点 。

? A.至少含有?m/2?棵子树 B.至多含有?m/2?棵子树 ? C.至少含有?m/2?棵子树 D.至多含有?m/2?棵子树

题9.6

使用哈希函数H(x)=x把一个整数值转换成散列表下标,现要把数据1、13、12、34、38、33、27、22插入到散列表,画出使用线性探测再散列构造的散列表。

题9.7

已知序列45,15,20,35,25,60,18,50,请画出依次插入该序列的的AVL树。 题10.1

? 在下列方法中,所需辅助存储量最多的是 ,所需辅助存储量最少的

是 ,平均速度最快的是 。 ? A.快速排序 B.归并排序 C.堆排序 题10.2

? 在文件“局部有序” 的情况下,最佳内部排序是 。

? A.直接插入排序 B.快速排序 C.简单选择排序

题10.3

快速排序在最坏情况下时间复杂度是O(n2),比 的性能差。 A.堆排序 B.起泡排序 C.选择排序

题10.4

? 若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的方

法是 。

? A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

题10.5

判别序列(12,70,33,65,24,56,48,92,86,33)是否为小顶堆,如果不是,则把它调整为小顶堆。

不成功的平均查找长度是多少。

题9.2

? 若在线性表中采用折半查找法,该线性表应该( )。 ? A.元素按值有序 B.采用顺序存储结构 ? C.元素按值有序,且采用顺序存储结构

? D.元素按值有序,且采用链式存储结构

题9.3

已知序列17,31,13,11,20,35,25,8,4,24,40,27,请画出该序列的二叉排序树,并分别给出下列操作后的二叉树:1)插入数据9,2)删除结点17。

题9.4

含有12个结点的平衡二叉树的最大深度是 (设根结点深度为1)。 题9.5

? 在非空m阶B-树上,除根结点以外的所有其他非终端结点 。

? A.至少含有?m/2?棵子树 B.至多含有?m/2?棵子树 ? C.至少含有?m/2?棵子树 D.至多含有?m/2?棵子树

题9.6

使用哈希函数H(x)=x把一个整数值转换成散列表下标,现要把数据1、13、12、34、38、33、27、22插入到散列表,画出使用线性探测再散列构造的散列表。

题9.7

已知序列45,15,20,35,25,60,18,50,请画出依次插入该序列的的AVL树。 题10.1

? 在下列方法中,所需辅助存储量最多的是 ,所需辅助存储量最少的

是 ,平均速度最快的是 。 ? A.快速排序 B.归并排序 C.堆排序 题10.2

? 在文件“局部有序” 的情况下,最佳内部排序是 。

? A.直接插入排序 B.快速排序 C.简单选择排序

题10.3

快速排序在最坏情况下时间复杂度是O(n2),比 的性能差。 A.堆排序 B.起泡排序 C.选择排序

题10.4

? 若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的方

法是 。

? A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

题10.5

判别序列(12,70,33,65,24,56,48,92,86,33)是否为小顶堆,如果不是,则把它调整为小顶堆。

本文来源:https://www.bwwdw.com/article/5typ.html

Top