数据结构习题库

1、知识点：01绪论02顺序表03链表04栈05链队列06循环队列07串08数组的顺序表示09稀疏矩阵10广义表11二叉树的基本概念12二叉树遍历、二叉树性质13树、树与二叉树的转换14 赫夫曼树15 图的定义、图的存储16 图的遍历17 图的生成树18 静态查找（顺序表的查找、有序表的查找）19动态查找（二叉排序树、平衡树、B树）20哈希查找21插入排序（直接插入、折半插入、2路插入、希尔排序）22选择排序（简单选择、树形选择、堆排序）23快速排序、归并排序101A1(1).数据的逻辑结构是(A)。A.数据的组织形式B.数据的存储形式C.数据的表示形式D.数据的实现形式101A1(2).组成数据

2、的基本单位是(C)。A.数据项B.数据类型C.数据元素D.数据变量101B1(3).与顺序存储结构相比，链式存储结构的存储密度(B)。A.大B.小C.相同D.以上都不对101B2(4).对于存储同样一组数据元素而言，(D)。A.顺序存储结构比链接结构多占空间B.在顺序结构中查找元素的速度比在链接结构中查找要快C.与链接结构相比，顺序结构便于安排数据元素D.顺序结构占用整块空间而链接结构不要求整块空间101B2(5).下面程序的时间复杂度为(B)。x=0;for(i=1;i<n;i+)for(j=i+1;j<=n;j+)x+;A.0(VF)B.O(n2)C.O(1)D.O(n)101

3、B2(6).下面程序的时间复杂度为(C)。for(i=0;i<m;i+)for(j=0；j<n；j+)Aij=i*j；A.0(R)B.0(n2)C.0(mxn)D.0(m+n)101C2(7).下面程序段的执行次数为(B)。for(i=0;i<n-1;i+)for(j=0；j>i；j+)state;A.n(n+1)/2B.(n-1)(n+2)/2C.n(n+1)/2D.(n-1)(n+2)101D3(8).下面程序的时间复杂度为(A)。for(i=0;i<m;i+)for(j=0；j<t；j+)cij=0；for(i=0;i<m;i+)for(j=0；

4、j<t；j+)for(k=0;k<n;k+)cij=cij+aik*bkj；A.0(mxnxt)B.0(m+n+t)C.0(m+nxt)D,0($t+n)102A1(9).顺序表的特点是(B)。A.表中元素的个数为表长B.按顺序方式存储数据元素C.逻辑结构中相邻的结点在存储结构中仍相邻D.按表中元素的次序存储102C2(10).设顺序表共有n个元素，用数组elem存储，实现在第i个元素之前插入一个元素e的操作，其主要语句为(D)。A.F0Rj=nD0WNT0iD0elemj=elemj+1;elemi=e;B.F0Rj=iT0nD0elemj=elemj+1;elemi=e;C.F

5、ORj=iTOnDOelemj+1=elemjelemi=e;D.FORj=nDOWNTOiDOelemj+1=elemj;elemi=e;102D2（11）.顺序表有5个元素，设在任何位置上插入元素是等概率的，则在该表中插入一个元素时所需移动元素的平均次数为（C）。A.3B.2C.2.5D.5102D2（12）.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（C）。A.9B.4.5C.7D.6102D3（13）.设顺序表有19个元素，第一个元素的地址为200,且每个元素占3个字节，则第14个元素的存储地址为（B）。A.236B.239C.242D.245102D2（14

6、）.设顺序表的第5个元素的存储地址为200,且每个元素占一个存储单元，则第14个元素的存储地址为（B）。A.208B.209C.210D.214103D3（15）.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p->llink和p->rlink表示，则下列等式中（D）成立。A.p=p->llinkB.p=p->rlinkC.p=p->llink->llinkD.p=p->llink->rlink103A1（16）.线性表采用链式存储时，其地址（D）。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可

7、以103B1（17）.线性表是（A）。A.一个有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空103B1（18）.链式存储的线性表中的指针指向其（B）。A.前趋结点B.后继结点C.物理前趋D.物理后继103C2（19）.设在链式存储的线性表中，设结点结构为datalink|,欲在p结点后插入一个结点q的关键步骤为（A）。A.q->link=p->link;p->link=q;B.p->link=q->link;p->link=q;C.q->link=p->link;q->link=p;D.

8、p->link=q->link;q->link=p;103C3（20）.设有指针head指向的带表头结点的单链表，现将指针p指向的结点插入表中，使之成为第一个结点，其操作是（A）（其中，p->next、head->next分别表示p、head所指结点的链域）。A.p->next=head->next;head->next=p;B.p->next=head->next;head=p;C.p->next=head；head=p；D.p->next=head；p=head；104A1（21）.在栈中，下列说法正确的是（A）。A.

9、每次插入总是在栈顶，每次删除也总是在栈顶。B.每次插入总是在栈顶，每次删除总是在栈底。C.每次插入总是在栈底，每次删除总是在栈顶。D.每次插入总是在栈底，每次删除也总是在栈底。104B2（22）.设有一个栈，按A、B、C的顺序进栈，则下列（C）为不可能的出栈序列。A.ABCB.CBAC.CABD.ACB104B2（23）.设有一个栈，按A、B、CD的顺序进栈，则下列（D）为可能的出栈序列。A.DCABB.CDABC.DBACD.ACDB104A2（24）.顺序栈的上溢是指（B）。A.栈满时作退栈运算B.栈满时作进栈运算C.栈空时作退栈运算D.栈空时作进栈运算104D3（25）.顺序栈S中top

10、为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（D）。A.s.elemtop=e;s.top=s.top+1;B.s.elemtop+1=e;s.top=s.top+1;C.s.top=s.top+1;s.elemtop+1=e;D.s.top=s.top+1；s.elemtop=e；104C2(26).设有5个元素A,B,C,D,E顺序进栈(进栈过程中可以出栈)，出栈后依出栈次序进入队列，已知其出队次序为D,C,E,B,A,则该栈容量必'定不小于(C)。A.2B.3C.4D.5104B2(27).设栈S的初始状态为空，现有五个元素组成的序列1

11、,2,3,4,5,对该序列在栈S上依次进行PUSHPUSHPOPPUSHPOPPUSHPUSHB作，出栈的元素序歹U是(C)。A.5,4,3,2,1B,2,1C,2,3D.3,4104B2(28).在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为(C)。A.top不变B.top=0C.top-D.top+104D3(29).向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行(B)。A.hs->next=s;B.s->next=hs;hs=s;C.s->next=hs->next;hs->nex

12、t=s;D.s->next=hs;hs=hs->next;105A1(30).在队列中，下列说法正确的是(A)。A.每次插入总是在队尾，每次删除总是在队头。B.每次插入总是在队尾，每次删除也总是在队尾。C.每次插入总是在队头，每次删除也总是在队头。D.每次插入总是在队头，每次删除总是在队尾。105D3(31).在带头结点的链队列q中，用q.front表示队头指针，q.rear表示队尾指针，结点结构为|data|next，删除链队列的队头结点的主要语句为(B)。A.s=q.front;q.front->next=s.next;B.s=q.front->next;q.fro

13、nt->next=s.next;C.s=q.front->next;q.front=s.next;D.s=q;q.front->next=s.next;106C3(32).循环队列sq中，用数组elem存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，队列的最大容量为MAXSIZE则队列满的条件为(D)。A.sq.front=sq.rearB.sq.front=sq.rear+1C.(sq.front+1)modMAXSIZE=sq.rearD.(sq.rear+1)modMAXSIZE=sq.front106C2(33).循环队列

14、sq中，用数组elem存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，队列的最大容量为MAXSIZE则在队列未满时元素x入队列的主要操作为(A)。A.sq.rear=(sq.rear+1)modMAXSIZE;sq.elemsq.rear=x;B.sq.elemsq.rear=x;sq.rear=(sq.rear+1)modMAXSIZE;C.sq.front=(sq.front+1)modMAXSIZEsq.elemsq.front=x;D.sq.elemsq.front=x;sq.front=sq.front+1;106B2(34).循环队列s

15、q中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20,sq.rear为12,则当前队列中的元素个数为(D)。A.8B.16C.17D.18106B2(35).设循环队列的元素存放在一维数组Q0-30中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应指向(B)元素。A.Q4B.Q5C.Q14D,Q15105A1(36).队列操作的原则是(A)。A.先进先出B.后进先出C.只能进行插入D.只能进行删除105B2(37)

16、.一个队列的入列序列是1234,则队列的输出序列是(B)。A.4321B.1234C.1432D,3241108C2（38）.设6行8列的二维数组A6X8=（a。）按行优先顺序存储，若第一个元素的存储位置为200,且每个元素占3个存储单元，则元素a54的存储位置为（B）。A308B305C266D269109C2（39）.设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，aii为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B）。Ai3B33Ci8D40108A1（40）.设二个数组为A0-7、B-5-2,3-8,则这两个数组分别能存放的字符的最大个数是（C）

17、。A7和35Bi和5C8和48Di和6i08C3（4i）二维数组Mi，j的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4,列下列j的范围从0到5。M按行存储时元素M3,5的起始地址与M按列存储时元素（B）的起始地址下同。AM2，4BM3，4CM3，5DM4，4108C2（42）.设二维数组为M0-8,0-10,每个元素占2L个存储单元，以行序为主序存储，第一个元素的存储位置为P。存储位置为P+50L的元素为（A）。AM2，3BM2，2CM3，3DM3，4108C2（43）.设二维数组A的维数界偶定义为1-8,0-10,起始地址为LOG每个元素占2L个存储单元，以行序为

18、主序存储方式下，某数据元素的地址为LOC+50L则在列序为主序存储方式下，该元素的存储地址为（D）。ALOC+28LBLOC+36LCLOC+50LDLOC+52L109B2（44）.数组A1-40,130采用三元组表示，设数组元素与下标均为整型，则在非零元素个数小于（D）时，才能节省存储空间。A1200B401C399D400108A1（45）一维数组通常采用顺序存储结构，这是因为（C）。A.一维数组是一种线性数据结构B.一维数组是一种动态数据结构C.一旦建立了数组，则数组中的数据元素之间的关系不再变动D.一维数组只能采用顺序存储结构109A1（46）对稀疏矩阵进行压缩存储的目的是（B）。A

19、方便存储B节省存储空间C方便运算D节省运算时间108D3（47）.设二维数组a0-5,0-6按行存储，每个元素占d个存储单元，如果每个元素改为2d个存储单元，起始地址不变，则元素a2,6的存储地址将要增加（A）个存储单元。A20dB21dC38dD39d108B2（48）一维数组与线性表的区别是（A）。A前者长度固定，后者长度可变B后者长度固定，前者长度可变C两者长度均固定D两者长度均可变107A1（49）下列关于串的叙述中，不正确的是（B）。A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储107B2（50）以下论断正确的是（A）

20、。A.是空串，是空白串B."BEIJING”是“BEIJING”的子串C“something”<“Somethig”D”BIT”=”BITE”107B2（51）.字符串“VARTYPEunsignedint”若采用动态分配的顺序存储方法需要（C）个字节（假设每种数据均占用2个字节）。A38B动态产生，视情况而定C40D42111A1（52）.由3个结点可以构造出（A）种不同形态的有向树。A .111A1A .D .2 B (53).2 B.3 C . 4 D . 5卜列树的度为(B)。.3 C . 5112C2A .111B2(54) .3 B(55) .含10个结点的二叉树中

21、，度为2的结点有（A个。.4 C . 5 D .6对一棵有100个结点的完全二叉树按层编号，则编号为 49的结点，它的左孩子的编号为（A）。A.98B.99C.97D.50112B2（56）.一棵深度为8（根的层次号为1）的满二叉树有（B）个结点。A.256B.255C.128D.127112C3（57）.设二叉树根结点的层数为1,若一棵高（深）度为h的二叉树只有度为0与度为2的结点,则其结点数至少为（B）。A .112C2A)。hB.2h-1C.2hD.2h+1（58）.对下列二叉树进行先根次序遍历，所得次序为（A .112D3A .112A1ABCDEFBCDAFE D. DCBFEA（5

22、9） . 一棵二叉树的前（先）序序列为ABCDEFG则它的中序序列不可能为（CBDAFEG B . DCBAEFG C . CDBAGEF D（60） .若先序遍历二叉树的结果为结点序列A, B,C)。.BDCAFGEC,则有（Q棵不同的二叉树可以得到这一结果。A .111B2A .112C2A .114B2A .C .3 B (61). n B (62). n B (63).4 C . 5 D . 6具有n个结点的二叉树，有（B）条边。.n-1 C , n+1 D . 2n在具有n个结点的二叉树的二叉链表表示中,2n个孩子指针域中，只用到（B）个域。D . 111D3.n-1 C , n+1

23、 D . 2n 对哈夫曼树，下列说法错误的是（哈夫曼树是一类带树路径长度最短的树OB）。B .给出一组数，构造的哈夫曼树唯一。给出一组数，构造的哈夫曼树的带树路径长度不变。哈夫曼树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。（64） .假定在一棵二叉树中，双分支结点数为15个，单分支结点数为 30个，则叶子结点数为(B)。A .113C3A .114B215 B . 16 C . 17 D . 47（65） .假定一棵三叉树的结点数为50,则它的最小高度为（C）。3 B . 4 C . 5 D . 6（66） .由带权为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，该树的带权

24、路径长度为（23 B . 37 C . 46 D . 44D)。112C2 （67）.二叉树的先序遍历为 EFHIGJK中序遍历为HFIEJKG则该二叉树根的右子树的根是A.E B . F C.G D.H(C)。111A1 （68）.在完全二叉树中，若一个结点是叶结点，则它没有（C）。A.左孩子结点B.右孩子结点C.左孩子和右孩子结点D.左孩子结点，右孩子结点和兄弟结点113B2(69).(B)二叉树，可以唯一地转化成一棵一般树。A.根结点无左孩子B.根结点无右孩子C.根据结点有两个孩子D.没有一棵111C2(70).具有65个结点的完全二叉树其深度为(B)。A.8B.7C.6D.5112C2

25、(71).某二叉树的先序序列和后序序列正好相反，则该二叉树一定是(B)的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子113A1(72).下面叙述中，不正确的是(C)。A.线性表中除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继B.树中有且仅有一个结点没有前驱C.环形队列中任何一个元素都有且仅有一个直接前驱和一个直接后继D.在树中，一个结点可以有多个直接后继C)。114B2(73).有m个叶子结点的哈夫曼树，其结点总数是(A . 2m B . 2m+1 C . 2m-1D . 2 (m+D011115A1 (74).设图的

26、邻接矩阵为001,则该图有(A)个顶点。01011 ,则该图为(A)。0A.3B.4C.6D.901115B2(75).设图的邻接矩阵为0001A.有向图B.无向图C.强连通图D.完全图3<C . 10 D . 20115B2(76).设图的邻接链表如下图所示，则该图有(B)条边。1 V122 V213 V314 V41A.4B.5115C2(77).设有6个结点的无向图，该图至少应有(B)条边才能确保是一个连通图。A.5B.6C.7D.8V1出116D3(78).已知一有向图的邻接表存储结构如下，则根据有向图的深度优先遍历算法，从顶点A.MV2V3V5V4B.V1V3V,MMC.VV2

27、V4V5V3D.V1V4V3VV2119C3(79).下列图的深度优先遍历序列为(B)。A.ABCDEFGHB.ABDHECFGC.ABEDHCFGD.ABCFGEDH115B1(80).对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为(D)。A.nB.(n-1)2C.(n+1)2D.n2118B2(81).对含n个记录的顺序表进行顺序查找，在最坏情况下需要比较(B)次。A.n-1B.nC.(n+1)/2D.n(n-1)/2118B2(82).对含n个记录的有序表进行折半查找，设每个记录的查找概率相等，则平均查找长度的数量级为(C)。2、10个数据元素(50, 30,119C3 (84

28、).已知15, 35, 70,的方法生成一棵二叉排序树后，在查找成功的情况下，查找每个元素的平均比较次数(又称平均查 找长度)为(C)。AO(n)B.O(n)C.O(log2rI)D.O(1)D,以上都不是65,95,60,25,40),按照依次插入结点A.B.C.D.118C3(85).在顺序存储的线性表R0-29上进行分块查找(设分为5块)的平均查找长度为(D)。A.6B.11C.5D.120D3(86).已知一个线性表(38,25,74,63,52,48),假定采用h(k)=k%7计算散列地址进行散列存储，若引用线性探测的开放定地址法解决冲突，则在该散列表上进行查找的平均查找长度为(C)

29、。A.B.C.2D.119A1(87).在一个3阶的B-树上，每个结点包含的子树相同，最多为(C)。A.1B.2C.3D.4120B2(88).设散列地址空间为0m-1,k为关键字，用P去除k,将余数作为k的散列地址，即：h(k)=k%P为了减少发生冲突的可能性，一般取P为(B)。A.小于m的最大奇数B.小于m的最大素数C.小于m的最大偶数D.小于m的最大合数120C3(89).设散列表表长m=14,散列函数为h(k)=k%11,表中已有4个记录，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是(D)。012345678910111213A8B3C5D9119C3（90）已知8个元

30、素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（C）。A4B5C6D7121B1（91）直接插入排序算法的时间复杂度为（B）。2AO（n）BO（n）CO（log2n）DO（1）121B2（92）设记录关键字序列为（84，67，21，50，33，79），采用对半插入排序方法自小到大进行排序时，记录的移动次数为（C）。A9B10C19D25123D3（93）.下列四个序列中，（D）不是快速排序第一趟的可能结果。A68，11，69，23，18，70，7393B1168，69，23，18，70，73，93C68，11，69，23，18709

31、3，73D18，11，239368，70，69，73122C3（94）.下列四个关键字序列中，（C）不是堆。A05，23，16，68，94，72，71，73B05，16，23，68，94，72，71，73C05，23，16，73，94，72，71，68D05，23，16，68，73，71，72，94123B2（95）从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（D）。A归并排序B选择排序C交换排序D插入排序123B2（96）在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（D）。AShell排序B冒泡排序C直接插入排序D直接选择排

32、序123B2（97）下列排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（B）。A选择B插入C冒泡D快速123C2（98）采用下列排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法有（A）。A选择和插入B冒泡和快速C插入和快速D选择和冒泡123D3（99）若用冒泡排序方法对序列10，14，26，29，41，52从大到小进行排序，需要进行（C）次比较。A5B10C15D25121C3（ 100） 用直接插入排序方法对下面四个序列进行排序，元素比较次数最少的是（C）。A94，32，40，90，80，46，21，69B32，40，21，46，69，94，90，80C21，3

33、2，46，40，80，69，90，94D90，69，80，46，21，32，94，40二、填空题101A1(1).数据结构按逻辑结构可分为两大类，它们分别是(线性结构和非线性结构)。101A1(2).算法的计算量的大小称为(计算的复杂度)。102B2(3).顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的(n/2)个元素。103A2(4).顺序表相对于链表的优点有(节省存储)和(随机存取)。103B2(5).线性表的长度是(表中数据元素的个数)。103D3(6)在带有头结点的双链表L中，指针p所指结点是第一个元素结点的条件是(

34、p=L->next;或L->next=p;)。103C3(7).某链表如下所示infolinkA若要删除值为C的结点，应做操作(p->link=p->link->link104A1(8).对于栈只能在(栈顶)插入和删除元素。104C2 (9).设有一空栈，现有输入序列1push后，输出序列是(2、3)。，2, 3, 4, 5, 6,经过 push, push, pop, push,pop, push,106B2 ( 10).有一个循环队列如下图，其队满条件是(rear=front )。front=(rear+1)%n ),队列空的条件是rearfront队尾指针队

35、头指针、，3109B2 (11). 一个稀疏矩阵为00 ,则对应的三元组线性表为(0, 2, 2),5(1, 0, 3),(2, 2 -1 ), (2, 3 5)。108C2 (12).设有二维数组 A0 9,0 - 19,其每个元素占两个字节，数组按列优先顺序存储，第个元素的存储地址为100,那么元素A6, 6的存储地址为(232)。112B1 (13).在一棵二叉排序树上按(中序)遍历得到的结点序列是一个有序序列。111C3 (14).对于一棵具有 n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中(n-1 )个用于链接孩子结点。112B24, 2, 5, 6,

36、3, 1 )。115B1117C3(15).对于下面的二叉树，按后序遍历得到的结点序列为(0)边。(17).对下列图1624它的生成树有(6)棵。118C3(18).假定在有序表R019上进行二分查找，则比较三次查找成功的结点数为(4)。120D3(19).设有两个散列函数H1(K)=Kmod13和H2(K)=Kmod11+1,散列表为T012,用双重散列法(又称二次散列法)解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量。假定某一时刻散列表T的状态为：012345678910111280，)534下一个被插入白关键码为42,其插入位置是(0)。122C3

37、(20).已知一棵二叉排序树如下图所示，则在查找成功的情况下查找每个元素的平均查找长度80509040100607三、完形填空题102D2(1).设顺序存储的线性表存储结构定义为：structsequnceELEMTPelemMAXSIZE;intlen;/*线性表长度域*/将下列简单插入算法补充完整。voidinsert(structsequnce*p,inti,ELEMTPx)v=*p;if(i<1)|(i>+1)printf("Overflow");elsefor(j=；j>=i；j-)j+1=j；i=x;=+1；103D3(2).设线性链表的存储结构如下：structnodeELEMTPdata;/*数据域*/structnode*next;/*指针域*/则把新结点插在试完成下列在链表中值为x的结点前插入一个值为y的新