当前位置:文档之家› 数据结构习题库

数据结构习题库

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.快速排序、归并排序 2

101A1(1).数据的逻辑结构是(A)。 A.数据的组织形式 B.数据的存储形式 C.数据的表示形式 D.数据的实现形式 101A1(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 for(j=i+1;j<=n;j++) x++; A.O(n) B.O(n2) C.O(1) D.O(n) 101B2(6).下面程序的时间复杂度为(C)。

for(i=0;i for(j=0;j A[i][j]=i*j; A.O(m2) B.O(n2) C.O(m×n) D.O(m+n) 101C2(7).下面程序段的执行次数为(B)。 for(i=0;i for(j=0;j>i;j++) state; A.n(n+1)/2 B.(n-1)(n+2)/2 C.n(n+1)/2 D.(n-1)(n+2) 101D3(8).下面程序的时间复杂度为(A)。 3

for(i=0;i for(j=0;j c[i][j]=0; for(i=0;i for(j=0;j for(k=0;k c[i][j]=c[i][j]+a[i][k]*b[k][j]; A.O(m×n×t) B.O(m+n+t) C.O(m+n×t) D.O(m×t+n) 102A1(9).顺序表的特点是(B)。 A.表中元素的个数为表长 B.按顺序方式存储数据元素 C.逻辑结构中相邻的结点在存储结构中仍相邻 D.按表中元素的次序存储 102C2(10).设顺序表共有n个元素,用数组elem存储,实现在第i个元素之前插入一个元素e的操作,其主要语句为(D)。 A.FOR j=n DOWNTO i DO elem[j]=elem[j+1]; elem[i]=e; B.FOR j=i TO n DO elem[j]=elem[j+1]; elem[i]=e; C.FOR j=i TO n DO elem[j+1]=elem[j]; elem[i]=e; D.FOR j=n DOWNTO i DO elem[j+1]=elem[j]; elem[i]=e; 102D2(11).顺序表有5个元素,设在任何位置上插入元素是等概率的,则在该表中插入一个元素时所需移动元素的平均次数为(C)。 A.3 B.2 C.2.5 D.5 102D2(12).设顺序表有9个元素,则在第3个元素前插入一个元素所需移动元素的个数为(C)。 A.9 B.4.5 C.7 D.6 102D3(13).设顺序表有19个元素,第一个元素的地址为200,且每个元素占3个字节,则第14个元 4

素的存储地址为(B)。 A.236 B.239 C.242 D.245 102D2(14).设顺序表的第5个元素的存储地址为200,且每个元素占一个存储单元,则第14个元素的存储地址为(B)。 A.208 B.209 C.210 D.214 103D3(15).设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p->llink和p->rlink表示,则下列等式中(D)成立。 A.p=p->llink B.p=p->rlink C.p=p->llink->llink D.p=p->llink->rlink 103A1(16).线性表采用链式存储时,其地址(D)。 A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可以 103B1(17).线性表是(A)。 A.一个有限序列,可以为空 B.一个有限序列,不可以为空 C.一个无限序列,可以为空 D.一个无限序列,不可以为空 103B1(18).链式存储的线性表中的指针指向其(B)。 A.前趋结点 B.后继结点 C.物理前趋 D.物理后继 103C2(19).设在链式存储的线性表中,设结点结构为 data link ,欲在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.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.每次插入总是在栈顶,每次删除也总是在栈顶。 B.每次插入总是在栈顶,每次删除总是在栈底。 C.每次插入总是在栈底,每次删除总是在栈顶。 D.每次插入总是在栈底,每次删除也总是在栈底。 104B2(22).设有一个栈,按A、B、C的顺序进栈,则下列(C)为不可能的出栈序列。 5

A.ABC B.CBA C.CAB D.ACB 104B2(23).设有一个栈,按A、B、C、D的顺序进栈,则下列(D)为可能的出栈序列。 A.DCAB B.CDAB C.DBAC D.ACDB 104A2(24).顺序栈的上溢是指(B)。 A.栈满时作退栈运算 B.栈满时作进栈运算 C.栈空时作退栈运算 D.栈空时作进栈运算 104D3(25).顺序栈S中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e进栈操作的主要语句为(D)。 A.s.elem[top]=e; s.top=s.top+1; B.s.elem[top+1]=e; s.top=s.top+1; C.s.top=s.top+1; s.elem[top+1]=e; D.s.top=s.top+1; s.elem[top]=e; 104C2(26).设有5个元素A,B,C,D,E顺序进栈(进栈过程中可以出栈),出栈后依出栈次序进入队列,已知其出队次序为D,C,E,B,A,则该栈容量必定不小于(C)。 A.2 B.3 C.4 D.5 104B2(27).设栈S的初始状态为空,现有五个元素组成的序列1,2,3,4,5,对该序列在栈S上依次进行PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH操作,出栈的元素序列是(C)。 A.5,4,3,2,1 B.2,1 C.2,3 D.3,4 104B2(28).在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为(C)。 A.top不变 B.top=0 C.top- - D.top++ 104D3(29).向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行(B)。 A.hs->next=s; B.s->next=hs;hs=s; C.s->next=hs->next;hs->next=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.front->next= s.next;

相关主题