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

数据结构练习题

数据结构练习题
数据结构练习题

练习题

一、选择题

1.顺序存储结构中数据元素之间的逻辑关系是由( C )表示的。

A、线性结构

B、非线性结构

C、存储位置

D、指针

2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。

A、顺序表

B、双链表

C、带头结点的双循环链表

D、单循环链表

3. 执行下面程序段时,语句S的执行次数为(D )。

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

for(j=0;j<=i;j++) S;

A)n2B)n2/2 C)n(n+1) D)(n+1)(n+2)/2

4 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素,则选择(A )存储方式最节省时间。

A)顺序表B)带头结点的双循环链表

C)单链表D)带尾结点的单循环链表

5.在长度为n的顺序表的第i个位置上插入一个元素(1≤ i ≤n+1),元素的移动次数为:(B)

A、 n – i

B、 n – i + 1

C、 i

D、 i – 1

6.非空的单循环链表由头指针head指示,p 指针指向链尾结点的条件是( A )。

A、p->next==head

B、p->next==NULL

C、p==NULL

D、p==head

7.下列选项中,(B )是链表不具有的特点。

A)插入和删除运算不需要移动元素

B)可以随机访问表中的任意元素

C)不必事先估计存储空间的大小

D)所需要的存储空间与线性表的长度成正比。

8.假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是(C )。

A)线性表B)树C)图D)集合

9.栈和队列的共同点是(C)

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

10.一个队列的入队序列是a,b,c,d,则该队列的出队序列是(C )。

A、d,c,b,a

B、a,d,c,b

C、a,b,c,d

D、b,c,d,a

11.带头结点的单链表h为空的判断条件是(D )。

A)h==NULL B)h->next== h

C)h!=NULL D)h->next== NULL

12. 下面关于串的叙述中,哪一个是不正确的?(C )

A)串是字符的有限序列B)串既可以采用顺序存储,也可以采用链式存储C)空串是由空格构成的串D)模式匹配是串的一种重要运算

13.判断一个最大容量为m的循环队列Q为空的条件是(A )。

A、Q->front==Q->rear

B、Q->front!=Q->rear

C、Q->front==(Q->rear+1)%m

D、Q->front!=(Q->rear+1)%m

14.在一棵树中,每个节点最多有( B )前驱节点?

A、0

B、1

C、2

D、任意多个

15.已知完全二叉树的第7层有10个叶子结点,则整个二叉树中结点数为(A )。

A) 73 B) 72 C) 63 D) 55

16. 下面的说法中,不正确的是(D)

A)对称矩阵只须存放包括主对角线元素在内的下(或上)三角的元素即可。

B)对角矩阵只须存放非零元素即可。

C)稀疏矩阵中值为零的元素较多,因此可以采用三元组表方法存储。

D)稀疏矩阵中大量值为零的元素分布有规律,因此可以采用三元组表方法存储

17.在一棵深度为k的满二叉树中,结点总数为( C )

A、2k-1

B、2k

C、2k-1

D、?log2k?+1

18.数组A中,每个元素的长度为3个字节,行下标从1到5,列下标从1到6,从首地址SA开始连续存放在存储器内,存放该数组至少需要的字节数是( A )。

A、90

B、70

C、50

D、301

19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点,则该图一定是(B)。

A)完全图 B)连通图C)有回路D)一棵树

20. 设计一个判别表达式中左右括号是否配对的算法,采用(A )数据结构最佳

A )栈B)链表C)顺序表D)队列

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

A、n-1

B、n(n-1)/2

C、n(n+1)/2

D、0

22.下面关于求关键路径的说法不正确的是( C )。

A、求关键路径是以拓扑排序为基础的。

B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同。

C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差。

D、关键活动一定位于关键路径上。

23.最小生成树指的是(C )。

A)由连通网所得到的边数最少的生成树

B)由连通网所得到的顶点数相对较少的生成树

C)连通网中所有生成树中权值之和为最小的生成树

D)连通网的极小连通子图

24.已知一个有向图的邻接矩阵表示,要删除所有从第i个结点发出的边,应该:( B )

A)将邻接矩阵的第i行删除B)将邻接矩阵的第i行元素全部置为0

C)将邻接矩阵的第i列删除D)将邻接矩阵的第i列元素全部置为0

25.适用于折半查找的表的存储方式及元素排列要求为( D)

A、链接方式存储,元素无序。

B、链接方式存储,元素有序。

C、顺序方式存储,元素无序。

D、顺序方式存储,元素有序。

26.下面给出的四种排序法中( D )排序法是不稳定性排序法。

A、插入

B、冒泡

C、归并排序

D、堆排序

27.静态查找与动态查找的根本区别在于(C )。

A) 它们的逻辑结构不一样B) 所包含的数据元素的类型不一样

C) 施加在其上的操作不同D) 存储实现不一样

28.顺序查找法适合于存储结构为( A )的线性表。

A)顺序存储结构或链式存储结构B)散列存储结构

C)索引存储结构D)压缩存储结构

29.下列四种排序中(D )的空间复杂度最大。

A) 插入排序B) 冒泡排序C) 堆排序D) 归并排序

30.快速排序在( C )情况下最不利于发挥其长处。

A、待排序的数据量太大

B、待排序的数据中含有多个相同值

C、待排序的数据已基本有序

D、待排序的数据数量为奇数

二、判断题

1.线性表的特点是每个元素都有一个前驱和一个后继。×

2.若一个广义表的表头为空表,则此广义表亦为空表。×

3.数组元素的下标值越大,存取时间越长。×

4.线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。×

5.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i-1 个结点。×

6.用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。√

7.广义表(a,b,c,d)的表尾是(b,c,d)。√

8.当一棵具有n个叶子结点的二叉树的WPL值为最小时,称其树为Huffman 树,且其二叉树的形状必是唯一的。×

9.树与二叉树是两种不同的树型结构。×

10.完全二叉树中,若一个结点没有左孩子,则它必没有右孩子。√

11.在AOV网络中如果存在环,则拓扑排序不能完成。√

12.每种数据结构都具备三个基本操作:插入、删除和查找。×

13.完全二叉树中,若一个结点没有左孩子,则它必是树叶。×

14.通常使用队列来处理函数或过程的调用。√

15.对一个堆,按二叉树层次进行遍历可以得到一个有序序列。√

16.如果一个串中的所有字符均在另一个串中出现,则说前者是后者的子串。×

17.给定一棵树,可以找到唯一的一棵二叉树与之对应。√

18.在一个大根堆中,最小元素不一定在最后。√

19.内排序中的快速排序方法,在任何情况下均可得到最快的排序效果。×

20.由树转换成二叉树,其根结点的右子树总是空的。×

三、填空题

1.在线性结构、树状结构和图结构中,数据元素之间分别存在着______________、______________和______________联系。(一对一一对多多对多)

2.在循环单链表L(L为头指针)中,指针p 所指结点为表尾结点的条件是__________________。(p->next==L)

3. 若用一个大小为6的数组来实现循环队列,且当前的rear和front的值分别为

0和3,当从队列中删除一个元素后,front的值为_______,再加入两个元素后,rear的值为_______。(4 2)

4.已知数组A[0..5,0..7]的每个元素占6个字节存储,将其按行优先次序存储在起始地址为1000的连续的内存单元中,则数组A的体积(即存储量)为_______个字节,元素A[1,4]的起始地址为_______。(288 1072)

5.广义表((a,b),(c,d))的表头是______________,的表尾是______________。

((a,b) ,((c,d))

6.有三个结点的二叉树共有________ 种形态。5

7.按13、24、37、90、53的次序形成平衡二叉树,则该平衡二叉树的高度是____________,其根为____________,在等概率下,查找成功的时候平均查找长度为__________。

(3 24 11/5)

8.假设一棵二叉树的先序遍历序列为ABCDEF,中序遍历序列为BCDAFE。则该二叉树的后序遍历序列为______________。

(DCBFEA)

1.数据结构中评价算法的两个重要指标是________________________________ 和________________________________。

(1)时间复杂度(2)空间复杂度

2.数据的逻辑结构主要分为__________、__________、__________ 和__________四种基本类型。

(1)集合(2)线性结构(3)树形结构(4)图状结构(网状结构)3.设有一个空栈,现有输入序列为1、2、3、4、5,经过push,push,pop,push,pop,push,push后,输出序列是_____________,栈顶元素是________。

(1)2、3 (2)5

4.串是一种特殊的线性表,其特殊性体现在________________________。

数据元素的类型是一个字符

6.在二叉树中,指针p所指结点为叶子结点的条件是________________________________。

p->lchild==NULL && p->rchlid==NULL

7.在AOV网络中如果存在环,则拓扑排序________(能,不能)完成。

不能

8.在用于表示有向图的邻接矩阵中,对第i行的元素进行累加,可得到第i个顶点的_____度,而对第j列的元素进行累加,可得到第j个顶点的______度。(1)出(2)入

四、应用题

1.有5个元素,其入栈次序为:A 、B 、C 、D 、E ,在各种可能的出栈次序中,以元素C 第一个出栈,D 第二个出栈的次序有哪几个? 共3个:CDEBA CDBAE CDBEA

2.假设用于通讯的电文仅由7个字符C1、C2、C3、C4、C5、C6、C7组成,它们在电文中出现的频率分别为8,12,4,5,26,16,10,请构造哈夫曼树,并给出对应字符的哈夫曼编码。

各字母的哈夫曼编码为:

C1:001 C2:101 C3:0000 C4:0001 C5:11 C6:01 C7:100

3.已知一个递增有序的查找表中有11个数据元素,请画出其折半查找的判定树,并求出在等概率情况下的查找成功的平均查找长度。

ASL SUCC =(1+2*2+3*4+4*4)/11=33/11=3

9 3 7 4

10 1 2 5 8 11

6

4.已知一组关键字序列为(20,30,70,15,8,12,18,63,19),请按哈希函数H(key)=key %11和链地址法处理冲突构造哈希表,并求出在等概率情况下的查找成功的平均查找长度。

在等概率情况下成功的平均查找长度为:

(1*5+2*2+3*1+4*1)/9=16/9

5.画出下面有向图的邻接表,并写出邻接表表示的图从顶点A出发的深度优先遍历序列。

邻接表如下:

深度优先遍历序列为ABCFED。

6.设待排序的关键字序列为{40, 27, 28, 12, 15, 50, 7},欲将该序列升序排列,请给出:

(1)快速排序第一趟的结果(以第一个记录为枢轴) 第一趟: [7 27 28 12 15] 40 [50]

(2)快速排序第二趟的结果(以第一个记录为枢轴)

7 [ 27 28 12 15] 40 [50] (3)堆排序时建成的初始大根堆

(4)堆排序第一趟的结果(即输出最大元素并将前6个元素重新调整成堆)

(5)基数排序第一趟的结果 40 50 12 15 27 7 28

7.对下图所示二叉树加上中序线索(直接加在原图上)。

40 40 27 28 15 7 12 28 27 7 15 50 12 50

8. 设用于某通讯设备中的电文仅由8个字母A 、B 、C 、D 、E 、F 、G 、H 组成,它们在电文中出现的频率分别为30,7,10,3,20,6,22,2,构造哈夫曼树,并给出对应字符的编码。

各字母的哈夫曼编码为:

A :00

B :0110

C :0111

D :01010

E :10

F :0100

G :11

H :01011

A

9. 请给出下图所示有向图的邻接矩阵。

0 0 0 0

1 0 0 0

1 1 0 0

1 1 1 0

10. 用普里姆(prim)算法构造以下网的最小生成树(假设从顶点①出发,试画出构造过程)。

11.已知一组关键字序列为(20,30,70,15,8,12,18,63,19),请按哈希函数H(key)=key %11和链地址法处理冲突构造哈希表,并求出在等概率情况下的查找成功的平均查找长度。

(4分)

在等概率情况下成功的平均查找长度为:

(1*5+2*2+3*1+4*1)/9=16/9

12. . 已知序列(503,87,512,61,908,170,897,275,653,426),欲将该序列作升序排列,请给出:

(1)希尔排序第一趟结果(增量d[1]=5)

170 87 275 61 426 503 897 512 653 908

(2)快速排序第一趟的结果(以第一个记录为枢轴)

[ 426 87 275 61 170 ]503 [ 897 908 653 512]

(3)2路归并排序第一趟排序的结果

87 503 61 512 170 908 275 897 426 653

(4)基数排序第一趟的结果

170 61 512 503 653 275 426 87 897 908

(5)堆排序时建成的初始大根堆

908 653 897 503 426 170 512 275 61 87

五、算法设计

1.设计算法,对带头结点的单链表实现就地逆置。并给出单链表的存储结构(数据类型)的定义。

参考答案:

typedef struct Lnode{

int data;

struct Lnode *next;

}Lnode,* linklist;

void reverse(linklist L)

{ linklist p, q;

p= L->next;

L->next=NULL;

while(p )

{ q=p->next;

p->next=L->next;

L->next=p;

p=q;

}

}

2.编写递归算法,将二叉树中所有结点的左、右子树相互交换。并给出算法中使用的二叉树的存储结构(数据类型)的定义。

typedef struct bitnode{

char data;

struct bitnode *lchild,*rchild;

}*BiTree;

void exchange(BiTree T)

{ BiTree p;

if(T)

{

p=T->lchild; T->lchild= T->rchild; T->rchild=p;

exchange (T->lchild);

exchange (T->rchild);

}

}

3. 编写递归算法,求二叉树的深度。并给出你在算法中使用的二叉树的存储结构(数据类型)的定义。

typedef struct bitnode{

char data;

struct bitnode *lchild,*rchild;

}bitnode,*bitree;

int heightbt(bitree t)

{ int n1,n2;

if(!t) return(0);

else {

n1= heightbt(t->lchild);

n2= heightbt(t->rchild);

return(n1>n2?n1+1:n2+1); }

}

4、应用队列功能设计层次遍历二叉树算法

int LayerOrder(BiTree bt)

/*层次遍历二叉树bt*/

{ SeqQueue * Q;

BiTree p;

InitQueue(Q);/*初始化空队列Q*/

if(bt= =NULL) return ERROR; /* 若二叉树bt为空树,则结束遍历*/ EnterQueue(Q, bt); /* 若二叉树bt非空,则根结点bt入队,开始层次遍历*/ while (!IsEmpty(Q)) /*若队列非空,则遍历为结束,继续进行*/

{

DeleteQueue(Q, &p); /*队头元素出队并访问*/

visit(p->data);

if(p-> LChild ) EnterQueue(Q, p-> LChild) ; /*若p的左孩子非空,则进队*/ if(p-> RChild ) EnterQueue(Q, p-> RChild) ; /*若p的右孩子非空,则进队*/ } /*while*/

return OK;

}

数据结构实验

实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法; 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找; 2.建立二叉排序树并对该树进行查找; 3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。 程序代码 #include using namespace std; int main() { int arraay[10]={1,2,3,4,5,6,7,8,9,10}; int binary_search(int a[10],int t); cout<<"Enter the target:"; int target; cin>>target; binary_search(arraay,target); return 0; } int binary_search(int a[10],int t) { int bottom=0,top=9; while(bottom

cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode; void inseart(PNode* root, keyType key) { PNode p = (PNode)malloc(sizeof(Node)); p -> key = key;

数据结构考试试题及答案

数据结构 一、单选题 1. 计算机算法指的是(b )。 A.程序B.问题求解步骤的描述C.调度方法D.排序方法 2. 以下数据结构中,(a )个是非线性数据结构。 A.树B.字符串C.队D.栈 3. 对于顺序存储的线性表,访问元素和插入元素的时间复杂度分别为:(c )。 A.O(n) O(n) B.O(n) O(1) C.O(1) O(n) D.O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点,正确的操作是(b )。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 6. 循环队列存储在数组A[0..m]中,则入队时的操作为( d ) A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为(d ) A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数为( b )A.9 B.11 C.15 D.不确定 9. 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当以列为主序存放时,元素A[5,8]的首地址为( b )。A.BA+141 B.BA+180 C.BA+222 D.BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A.n-1 B.n C.n/2 D.n+1 11.有关二叉树的下列说法正确的是( b ) A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 12.关键路径是AOE网中( a )。 A.从源点到汇点的最长路径B.从源点到汇点的最短路径 C.最长回路 D.最短路径(从源点到汇点的所有路径中,经过弧的数目最多的路径) 13.若查找每个记录的概率相等,则在具有n个记录的连续文件中采用顺序查找查找一个记录,其平均查找长度ASL为(c)。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n 14.就平均性能而言,目前最好的内部排序方法是(d ) A.冒泡排序B.希尔排序C.堆排序D.快速排序 15.已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(d )A.head(tail(LS)) B.tail (head (LS) C.head(tail(head(tail(LS)))) D.head(tail(tail (head (LS)))) 17.在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:( a ) A. 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) B. 在第i个结点后插入一个新结点(1≤i≤n)

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 1 ?在数据结构中,从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时,一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

数据结构实验报告

数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件,没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (2)算法指得就是()。 A)计算机程序???B)解决问题得计算方法 C)排序算法???D)解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得()。 A) 存储结构B) 逻辑结构C)算法D)操作 (4)从逻辑上可以把数据结构分为( )两大类。 A)动态结构、静态结构??B) 顺序结构、链式结构 C)线性结构、非线性结构???D)初等结构、构造型结构 (5)下列叙述中正确得就是()。 A)一个逻辑数据结构只能有一种存储结构 B)数据得逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是() ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为() i=0;s=0; while(s

数据结构试卷(五)及答案

数据结构试卷(五) 一、选择题(30分) 1.数据的最小单位是()。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为()。 (A) 40,50,20,95 (B) 15,40,60,20 (C) 15,20,40,45 (D) 45,40,15,20 3.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。 (A) 15,25,35,50,20,40,80,85,36,70 (B) 15,25,35,50,80,20,85,40,70,36 (C) 15,25,35,50,80,85,20,36,40,70 (D) 15,25,35,50,80,20,36,40,70,85 4.函数substr(“DATASTRUCTURE”,5,9)的返回值为()。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 5.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为()。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 6.设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为N l,……,度数为m的结点数为Nm,则N0=()。 (A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm 7.设有序表中有1000个元素,则用二分查找查找元素X最多需要比较()次。 (A) 25 (B) 10 (C) 7 (D) 1 8.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为()。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 9.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是()。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45 为基准而得到一趟快速排序的结果是()。 (A) 40,42,45,55,80,83 (B) 42,40,45,80,85,88 (C) 42,40,45,55,80,85 (D) 42,40,45,85,55,80 二、填空题(共30分) 1.设有一个顺序共享栈S[0:n-1],其中第一个栈项指针top1的初值为-1,第二个栈顶 指针top2的初值为n,则判断共享栈满的条件是____________________。 2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。

数据结构考试题库

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示,又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型,树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位,(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系,树形结构中元素之间存在(一个对多个)关系,图状结构中元素之间存在(多个对多个)关系。 ?6.数据结构是一门研究非数值计算的程序设计问题中:计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的,这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理,用心做精品2

A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中,从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时,要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答:有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素(1≤i≤n)时,需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时,其操作是(先移动队首指针,后取出元素)。 3.在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时,首先把(p->next)的值赋给q->next,然后(q->date)的值赋给p->next。 5.从一个栈删除元素时,首先取出(栈顶元素),然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理,用心做精品3

数据结构实验一 实验报告

班级::学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息(学号,,成绩)的顺序表和链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据进行查找,返回此学生的学号和成绩; (4) 根据指定的位置可返回相应的学生信息(学号,,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK;

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) A.(100,80,90,60,120,110,130) B.(100, 120, 110,130,80, 60,90) C.(100,60,80,90,120,110,130) D.(100,80, 60,90, 120, 130,110) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序

数据结构期末考试试题及答案

数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head!=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表:表中各结点都没有直接前趋和直接后继。 在顺序表中,只要知道(),就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中,使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中,向第i个元素之前插入一个新元素时,需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表

栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234,则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空

数据结构实验

长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.doczj.com/doc/7717315405.html,。提交时限:本次实验后24小时之内。 阅读程序,完成填空,并上机运行调试。 1、顺序栈,对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后,base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作(存储结构由SqStackDef.h 定义) Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数,即栈的长度, 编写此函数

数据结构题库教材

2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题,共24分) 1已知某字符串S中共有8种字符,各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98,所以,该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= [i/2」(取下整数),其中i为关键码 中第一个字母在字母表中的序号,采用链地址法处理冲突构造散列表,并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突,得到的开散列表如下: 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12

3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么? ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树,并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。

数据结构试卷带答案

数据结构试卷(一) 一、选择题(20分) 1.组成数据的基本单位是( 1.C )。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A是( C )。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3.数组的逻辑结构不同于下列(D)的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4.二叉树中第i(i≥1)层上的结点数最多有(C)个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(.A )。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是(.C )。 (A) 6 (B) 4 (C) 3 (D) 2 7.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为(C )。 (A) 100 (B) 40 (C) 55 (D) 80 8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为(8.B (A) 3 (B) 4 (C) 5 (D) 1 9.根据二叉树的定义可知二叉树共有(B)种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法,则(B )的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0:m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元 素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;。 2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________, 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指 针域,__________个空指针域。 4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编 号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构相关题库及答案

第三章栈和队列 一、判断题: 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列,头指针F指向队列的头结点,尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时,不会改变头指针的值。(易) 答案:1-4 √√×× 二、选择题: 1、一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST(最多元素为m0)为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST(最多元素为m0)为栈满的条件是D。A、top!=0 B、top= =0 C、top!=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行__ _C_。(不带空的头结点) (易) A、HS—>next=s;9 B、s—>next= HS—>next; HS—>next=s; C、s—>next= HS; HS=s; D、s—>next= HS; HS= HS—>next

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2. 物理结构是数据结构在计算机中的表示,又称为(存储结构)。 3. 数据元素的逻辑结构包括(线性)、(树)和图状结构3 种类型,树形结构和图状结构合称为(非线性结构)。 4. (数据元素)是数据的基本单位,(数据项)是数据不可分割的最小单位。 5. 线性结构中元素之间存在(一个对一个)关系,树形结构中元素之间存在(一个对多个)关系,图状结构中元素之间存在(多个对多个)关系。 ? 6.数据结构是一门研究非数值计算的程序设计问题中:计算机的(数据元素)以及它们之间的(关 系)和(运筹)等的学科。 7. 算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1. 数据的不可分割的基本单位是(D)。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的,这种说法(B)。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种(D)。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系

4. 在数据结构中,从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答:有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素(1< i产时,需向前移动(n-i)个元素。 2. 从循环队列中删除一个元素时,其操作是(先移动队首指针,后取出元素)。 3?在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为(p-> next)。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时,首先把(p->next)的值赋给q->next,然后(q->date)的值赋给p->next。 5. 从一个栈删除元素时,首先取出(栈顶元素),然后再使(栈顶指针)减1。 6. 子串的定位操作通常称做串的(模式匹配)。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第(六)次匹配成功。。 8. 顺序栈S 中,出栈操作时要执行的语句序列中有S->top(--);进栈操作时要执行的语句序列中有S->top(++)。

数据结构考试及答案()

数据结构考试及答案()

作者: 日期: 2

数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为(C) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D) A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为 (D )。 An B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行(D )o A s—link = p—link ;p—link = s; B p—link = s; s—link = q; C p—link = s—link ;s—link = p; D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用(C )方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p,求p在t中首次出现的位置的运算叫做(B )o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j] 占用3个存储字,行下标i从1到8,

列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放 该数组至少需要的存储字数是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ,则出队列顺序为(C )。 10、在循环队列中用数组A[0.. m-1]存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是( D )。 A ( front - rear + 1) % m B (rear - front + 1) %m C ( front - rear + m) % m D ( rear - front + n) % m 11、一个数组元素a[i]与(A )的表示等价。 A * (a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为(C) for (i nt i=0;i

数据结构实验1

《数据结构》实验报告 实验序号:1 实验项目名称:概论

附源程序清单: 1. #include void main() { int i; int num[10]; int *p; for(i=0;i<=9;i++) num[i]=i+1; for(p=(num+9);p>=(num+0);p--) printf("%d ",*p); printf("\n"); }

2. #include void main() { void swap(int *a,int *b); int i; int a[10]; int *p,*max,*min; for(i=0;i<10;i++) scanf("%d",&a[i]); max=min=a; for(i=0;i<10;i++) { if(*maxa[i]) min=&a[i]; } p=a; swap(p,max); swap((p+9),min); for(p=a;p<=(a+9);p++) printf("%d ",*p); printf("\n"); } void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } 3. #include #include #include #include typedef struct { char num[5]; char name[20]; float score1; float score2; float score3; float average;

数据结构考试题

要求:所有的题目的解答均写在答题纸上(每张答题纸上要写清楚姓名、班号和学号),需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题(每小题2分,共20分) 1. 在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度(n 为问题规模)最小是 。 A.T 1(n)=nlog 2n+5000n B.T 2(n)=n 2-8000n C.T 3(n)= n n 2 log -6000n D.T 4(n)=7000log 2n 3. 设线性表有n 个元素,以下操作中, 在顺序表上实现比在链表上实现效率更高。 A.输出第i (1≤i ≤n )个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号 4. 设n 个元素进栈序列是p 1,p 2,p 3,…,p n ,其输出序列是1,2,3,…,n ,若p 3=3,则p 1的值 。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 5. 以下各种存储结构中,最适合用作链队的链表是 。 A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s (长度为n ,每个结点存储一个字符),查找元素值为ch 的算法的时间复杂度为 。 A.O(1) B.O(n) C.O(n 2) D.以上都不对 7. 设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是 。 A.872 B.860 C.868 D.864 8. 一个具有1025个结点的二叉树的高h 为 。 A.11 B.10 C.11~1025 D.12~1024 9. 一棵二叉树的后序遍历序列为DABEC ,中序遍历序列为DEBAC ,则先序遍历序列为 。 A.ACBED B.DECAB C.DEABC D.CEDBA 10. 对图1所示的无向图,从顶点1开始进行深度优先遍历;可得到顶点访问序列 。

相关主题
相关文档 最新文档