2024年1月4日发(作者：)

数据结构考试题及答案

【篇一：数据结构期末考试试题及答案】

txt>一、选择题

1. 评价一个算法时间性能的主要标准是( )。

a、算法易于调试 b、算法易于理解 c、算法的稳定性和正确性 d、算法的时间复杂度 a、可行性、可移植性和可扩充性 b、可行性、确定性和有穷性 c、确定性、有穷性和稳定性 d、易读性、稳定性和安全性 a、head==null b、head-next==null c、head-next==head d、head！=null a、线性表中的数据元素可以是数字、字符、记录等不同类型。 b、线性表中包含的数据元素个数不是任意的。 c、线性表中的每个结点都有且只有一个直接前趋和直接后继。 d、存在这样的线性表：表中各结点都没有直接前趋和直接后继。 a、基地址 b、结点大小 c、向量大小 d、基地址和结点大小 a、插入 b、删除 c、根据序号查找 d、根据元素值查找 a、n-i b、n-i+1 c、n-i-1 2. 计算机算法具备有输入、输出、（ ）等五个特性。 3. 带头结点的单链表head为空的判定条件是（ ）。 4. 以下关于线性表的说法不正确的是( )。 5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。 6. ( )运算中，使用顺序表比链表好。 7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（ ）个元素

d、i a、顺序表 b、单链表 c、循环链表 d、双向链表 a、都是先进后出 b、都是先进先出 c、只允许在端点处插入和删除元素 d、没有共同点 a、4 3 2 1 b、1 2 3 4 c、1 4 3 2 d、3 2 4 1 a、数据元素的类型不同 b、运算是否受限制 c、数据元素的个数不同 d、逻辑结构不同 a、循环队列 b、队列 c、链队列 d、顺序队列

8. ( )适合作为经常在首尾两端操作线性表的存储结构。 9. 栈和队列的共同点是（ ） 10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。 11. 队列与一般的线性表的区别在于( )。 12. “假上溢”现象会出现在( )中。

二、填空题

1．数据的逻辑结构被分为 集合、线性结构、树形结构和图结构。

2．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构。

3．下面程序段的时间复杂度是o（n）。

i=s=0;

while (sn)

{ i++;

s++;; }

4．树型结构和图形结构合称是非线性结构。

5．在长度为n的顺序存储线性表的第i个元素（1≤i≤n）之前插入一个元素时，

需要向后移动n-i+1个元素。

6．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，

需要向前移动n-i个元素。

7．指针p指向非空循环单链表head的尾结点，则p满足p-next=head。

8．已知l是带头结点的非空单链表，且p

的答案中选择合适的语句序列，实现删除p

① p-next = p-next -next;

② p=p-next-next;

③ while (p-next!=q) p=p-next;

④ while (p-next-next=q) p=p-next;

⑤ q=p;

⑥ q=p-next;

⑦ p=l;

⑧ l=l-next;

⑨ free(q);

9．在线性结构中，第一个结点无前驱结点，其余每个结点有且只有1个前驱结点。

10．单链表是线性表的链式存储表示。

11．栈是限定仅在表尾进行插入或删除操作的线性表。

12．在栈顶指针为hs的链栈中，判定栈空的条件是hs=null。

13．假设以s和x分别表示进栈和退栈操作，则对输入序列a、b、c、d、e进行一系列栈操作ss后，得到的输出序列为bceda。

14．设栈s和队列q的初始状态为空，元素a、b、c、d、e、f依次通过栈s，一个元素出栈后即若这6个元素出队列的顺序是b、d、c、f、e、a，则栈s的容量至少应该是3。

三、算法填空

1．已知一个顺序表中的元素按关键字值非递减有序，下列算法删除顺序表中关键字相同的多余元关键字不同的元素在表中只保留一个。

void purge_sq(sqlist la)

{

//删除顺序表la中关键字相同的多余元素，即使操作之后的顺序表中只保留操作之前表中所有按不相同的元素

k= -1; //k指示新表的表尾

for (i=0;;++i) //顺序考察表中每个元素

{j=0;

while (j=k [j]!=[i])

++j; //在新表中查询是否存在和[i]相同的元素

if (k= = -1||jk) //k= -1表明当前考察的是第一个元素

[++k]= [i];

}//for

=k+1; //修改表长

}//purge_sq

2．一个头指针为head的单链表，其中每个结点存放一个整数，以下算法将其拆分为两个单链表head使head 1中仅含有正整数，head 2中仅含有负整数。

ist head2)

{

//将头指针为head的单链表（带头结点）拆分为两个单链表head1和head2，

//使head1中仅含有正整数，head2中仅含有负整数

head1=(linklist)malloc(sizeof(lnode)); head1-next=null;

head2=(linklist)malloc(sizeof(lnode)) ; head2-next=null;

p=head-next;

while(p) { q=p-next;

if （p-data=0） {p-next=head1-next;

head1-next=p; }

else {p-next=head2-next;

head2-next=p;

}

p=q;

} //while

【篇二：《数据结构》期末考试试题及答案】

txt>(2003-2004学年第2学期)

贵州大学理学院数学系信息与计算科学专业

一、 单项选择题

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 (a)、正确性 (b). 可行性 (c). 健壮性 (d). 输入性

2．设s为c语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1；i=0；i--)

for(j=0；ji；j++) s； (a)、n2 (b). o(nlgn)(c). o(n)(d). o(n2) 3．折半查找法适用于（ ）。

（a）、有序顺序表（b）、有序单链表

（c）、有序顺序表和有序单链表都可以 （d）、无限制 4．顺序存储结构的优势是（ ）。（a）、利于插入操作 （b）、利于删除操作（c）、利于顺序访问 （d）、利于随机访问

5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。

（a）、k-1（b）、k（c）、k-1和k （d）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）

（a）、11 （b）、13（c）、48（d）、37 7．图的depth-first

search(dfs)遍历思想实际上是二叉树（ ）遍历方法的推广。（a）、先序 （b）、中序（c）、后序 （d）、层序 8．在下列链队列q中，元素a出队的操作序列为（）

（（b）、p=-next; -next=p-next; （c）、p=-next; p-next= -next; （d）、p=q-next; q-next=p-next;

9． huffman树的带权路径长度wpl等于（ ）

（a）、除根结点之外的所有结点权值之和 （b）、所有结点权值之和 （c）、各叶子结点的带权路径长度之和（d）、根结点的值

10．线索二叉链表是利用（）域存储后继结点的地址。

（a）、lchild （b）、data（c）、rchild（d）、root

二、填空题

1． 逻辑结构决定了算法的 ，而存储结构决定了算法的。

2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。

3． 线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为l，元素ai

的存储地址loc(ai)为

4． 已知一双向链表如下(指针域名为next和prior)：

现将p所指的结点插入到x和y结点之间，其操作步骤为： ；

；； ； 5．n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。 6．已知一有向无环图如下：

任意写出二种拓扑排序序列：、。 7．已知二叉树的中序遍历序列为bca，后序遍历序列为cba，则该二叉树的先序遍历序列为 ，层序遍历序列为 。

三、应用题

1． 设散列函数h(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分) (1) 构造hash表。

(2) 分别求查找成功和不成功时的平均查找长度。

2． 给定表（19,14,22,15,20,21,56,10）.（8分） （1） 按元素在表中的次序，建立一棵二叉排序树

（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。

（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。 3． 已知二个稀疏矩阵a和b的压缩存储三元组表如下：

写出a-b压缩存储的三元组表。（5分）

4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)

5． 已知一网络的邻接矩阵如下，求从顶点a开始的最小生成树。(8分，要有过程)

ab cde f

a??651???

?b?6??53???

c?5??7?2???d?157?64?e??3?6?6???f????246???

（1）求从顶点a开始的最小生成树。

（2）分别画出以a为起点的dfs生成树和bfs生成树。

6把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。

（1） 画出对应的huffman树。 （2） 计算带权路径长度wpl。

（3） 求a、b、c、d、e、f的huffman编码。

7． 已知有如下的有向网：

求顶点a到其它各顶点的最短路径（采用dijkstra算法，要有过程）。（6分）

三、 设计题（30分，每题10分,用c语言写出算法，做在答题纸

上）

1． 已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下： #define list_init_size 100//顺序表初始分配容量

typedef struct {

elemtype*elem; //顺序存储空间基址

int length; //当前长度（存储元素个数） }sqlist;

设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：status

listdelete(sqlist l,elemtype x){

……

}

2．设顺序栈如左图所示。

其中结点定义如下：

typedef struct {

elemtype *base; //栈底指针 elemtype *top;//栈顶指针

}stack;

设计算法，将栈顶元素出栈并存入e中． base

3．设二叉链树的类型定义如下： typedef int elemtype;

typedef struct node{ elemtype data;

struct node *lchild, *rchild;}binnode, *bintree; 试写出求该二叉树叶子结点数的算法:

status countleaves(bintree root,int n){//n is the number of

leaves

……

}

答案：

选择题（每题1分）

1、c 2、d 3、a 4、d 5、c 6、d 7、a 8、b 9、c 10、c 一、填空题 1．设计、实现 2．特殊、栈顶

3．loc（a1）+(i-1)*l

4．p-next=q-next;q-next-prior=p; q-next=p;p-prior=q; 5．n(n-1)/2、n-1

6．adcbfeg、abcdeffg 7．abc、abc 二、应用题

（2）查找成功的平均查找长度：（1分）（5*1+1*2+2*3+1*7）/9=20/9

查找不成功的平均查找长度：（1分）

（2+1+9+8+7+6+5+4+3+2+1）/13= 2（1）、构造（3分）

(2)、10 14 15 19 20 21 22 56（2分） （3）、（3分）

【篇三：《数据结构》期末考试试题及答案】

txt>(2003-2004学年第2学期)

单项选择题1、c 2、d 3、a 4、d 5、c 6、d 7、a 8、b 9、c 10、c

一、

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (a)、正确性 (b). 可行性 (c). 健壮性 (d). 输入性 2．设s为c语言的语句,计算机执行下面算法时，算法的时间复杂度为（ d）。

for(i=n-1；i=0；i--)

for(j=0；ji；j++) s； (a)、n2 (b). o(nlgn)(c). o(n)(d). o(n2) 3．折半查找法适用于（ a）。

（a）、有序顺序表（b）、有序单链表

（c）、有序顺序表和有序单链表都可以 （d）、无限制 4．顺序存储结构的优势是（ d）。（a）、利于插入操作 （b）、利于删除操作（c）、利于顺序访问 （d）、利于随机访问

5．深度为k的完全二叉树，其叶子结点必在第（ c）层上。

（a）、k-1（b）、k（c）、k-1和k （d）、1至k

6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）

（a）、11 （b）、13（c）、48（d）、37

7．图的depth-first search(dfs)遍历思想实际上是二叉树（ a）遍历方法的推广。（a）、先序 （b）、中序（c）、后序 （d）、层序 8．在下列链队列q中，元素a出队的操作序列为（ a b）

（a）、p=-next; p-next= -next; （b）、p=-next; -next=p-next; （c）、p=-next; p-next= -next; （d）、p=q-next; q-next=p-next; 9． huffman树的带权路径长度wpl等于（ c）

（a）、除根结点之外的所有结点权值之和 （b）、所有结点权值之和 （c）、各叶子结点的带权路径长度之和（d）、根结点的值

10．线索二叉链表是利用（ c ）域存储后继结点的地址。 （a）、lchild （b）、data（c）、rchild（d）、root

二、填空题

1． 逻辑结构决定了算法的 设计，而存储结构决定了算法的 实现 。

2． 栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈顶

进行。

3． 线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为l，元素ai

的存储地址loc(ai)为

4． 已知一双向链表如下(指针域名为next和prior)：

现将p所指的结点插入到x和y结点之间，其操作步骤为： ；

；； ； 5．n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。 6．已知一有向无环图如下：

任意写出二种拓扑排序序列：、。 7．已知二叉树的中序遍历序列为bca，后序遍历序列为cba，则该二叉树的先序遍历序列为 ，层序遍历序列为 。

三、应用题

1． 设散列函数h(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分) (1) 构造hash表。

(2) 分别求查找成功和不成功时的平均查找长度。

2． 给定表（19,14,22,15,20,21,56,10）.（8分） （1） 按元素在表中的次序，建立一棵二叉排序树

（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。

（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。 3． 已知二个稀疏矩阵a和b的压缩存储三元组表如下：

写出a-b压缩存储的三元组表。（5分）

4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)

5． 已知一网络的邻接矩阵如下，求从顶点a开始的最小生成树。(8分，要有过程)

ab cde f

a??651???

?b?6??53???

c?5??7?2???d?157?64?e??3?6?6???f???246????

（1）求从顶点a开始的最小生成树。

（2）分别画出以a为起点的dfs生成树和bfs生成树。

6把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。

（1） 画出对应的huffman树。

（2） 计算带权路径长度wpl。

（3） 求a、b、c、d、e、f的huffman编码。 7． 已知有如下的有向网：

求顶点a到其它各顶点的最短路径（采用dijkstra算法，要有过程）。（6分）

三、 设计题（30分，每题10分,用c语言写出算法，做在答题纸

上）

1． 已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下： #define list_init_size 100//顺序表初始分配容量

typedef struct {

elemtype*elem; //顺序存储空间基址

int length; //当前长度（存储元素个数） }sqlist;

设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：status

listdelete(sqlist l,elemtype x){

……

}

2．设顺序栈如左图所示。

其中结点定义如下：

typedef struct {

elemtype *base; //栈底指针 elemtype *top;//栈顶指针

}stack;

设计算法，将栈顶元素出栈并存入e中． base

3．设二叉链树的类型定义如下： typedef int elemtype;

typedef struct node{ elemtype data;

struct node *lchild, *rchild;}binnode, *bintree;

试写出求该二叉树叶子结点数的算法:

status countleaves(bintree root,int n){//n is the number of

leaves

……

}

答案：

选择题（每题1分）

1、c 2、d 3、a 4、d 5、c 6、d 7、a 8、b 9、c 10、c 一、填空题 1．设计、实现 2．特殊、栈顶

3．loc（a1）+(i-1)*l

4．p-next=q-next;q-next-prior=p; q-next=p;p-prior=q; 5．n(n-1)/2、n-1

6．adcbfeg、abcdeffg 7．abc、abc 二、应用题

（2）查找成功的平均查找长度：（1分）

（5*1+1*2+2*3+1*7）/9=20/9

查找不成功的平均查找长度：（1分）

（2+1+9+8+7+6+5+4+3+2+1）/13= 2（1）、构造（3分）

(2)、10 14 15 19 20 21 22 56（2分） （3）、（3分）