计算机软件练习题汇总(3)

3. 4. 5. 6. 7.

线性结构与非线性结构有何差别？ 简述顺序表和链表之间的差异。 什么是排序方法的稳定性？

什么叫栈？它有哪些基本操作？各个基本操作的含义是什么？ 什么叫队列？它有哪些基本操作？各个基本操作的含义是什么？

五、综合题

1. 给出下列稀疏矩阵A的三元组表示法的存储模型。

A =

0 33 0 22 0 -15 0 0 3 0 0 0 0 0 0 -12 0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0 0 0 0 2

2. 给出下列稀疏矩阵所对应的三元组表示方法存储模型。

0?0129?0000???3000??00240?01800???1500?700?000??0140??000?000??000??0

3. 给出下列稀疏矩阵A的三元组表示法的存储模型。

4. 设单链表的结点为： typedef struct node

{ int data;

struct node *next } LinkList;

LinkList *p,q;

如果要求将由指针变量q所指向的结点插入到单向链接表中p所指向的结点之后，则应执行的语句是什么？要将p所指向的结点的数据部分修改为23，应执行的语句是什么？ 5. 对于给定的一组关键字:503,087,512,067,908,170,889,276,675,453；请按关键字递减

排序，写出直接插入排序、冒泡排序的各趟运行结果。

6. 某长度为10的有序表存储于一维结构数组中下标0~9的位置中,其中记录的关键键码值

依次是：5,10,18,21,33,47,48,55,80，125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“向下取整”的方法，写出折半查找的过程及查找结果。 7. 有序表中关键字序列为：5，10，19，21，31，37，42，48，55，150，现要查找k为

37及32的记录，写出其折半查找过程。

8. 设待排序的记录共7个，关键码分别为8，3，2，5，9，1，6。试用直接插入、直接选

择两种方法，以关键码的变化描述排序全过程（动态过程），要求按递减顺序排序。 9. 设待排序文件共有12个记录，其关键字依次分别是28，55，06，33，161，81，91，

11，25，55′，57，02，请按选择排序的思想写出降序排序的全过程。

10. 设有待排序的8个数据记录，其排序用关键字的取值依次是14，35，18，5，7，21，

35，8，请用简单选择排序法写出降序排序的每一趟结果。

11. 设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，

50，8，请按直接选择排序的思想写出升序及降序排序的每一趟结果。

12. 假设待排序的一批记录的关键字序列为{14，35，18，5，7，21}，请给出按照简单选择

排序方法依据关键字取值升序和降序两种情况下的排序过程。

13. 一个有序表的一批记录的关键字序列为（7，11，15，20，32，45，63，70，82，91），

存放在一个采用顺序存储结构表示的线性表中，其中数组元素的下标为0，?，9的位置上分别对应存储有序表的第一元素直到最后一个元素。在折半查找中，中间位置指示器的计算式子中采用取下整的方法，请给出查找关键字值为82和关键字值为13的记录的查找过程。

14. 某长度为10的有序表存储于一维结构数组中下标0~9的位置中，其中记录的关键码值

依次是：5,10,18,21,33,47,48,55,80,125，现要查找关键码值为18及83的记录，现规定在中间位置计算时采用“取下整”的方法，写出折半查找的过程及查找结果。

15. 设有待排序的8个数据记录，其排序用关键字的取值依次是68，45，20，90，15，10，

50，8，请用冒泡排序法写出升序排序的每一趟结果。

16. 对于给定的一组关键字: 50,38,27,16,97,76,53,66；按关键字递减排序，写出冒泡排

序的各趟运行结果。

六、算法分析与设计题

1. 下面给出的算法的功能是在顺序存储结构表示的线性表中插入一个数据元素，请画出算

法的流程图，在算法中对各个分支给出功能性注释。 #define Null 0

#define MaxSize 1024 typedef int DataType; typedef struct node {

DataType data[MaxSize]; int last; }SequenList;

int Insert(SequenList *L,DataType x,int i) {

SequenList *p; int j; p=L;

if(p->last==(MaxSize-1))

{

printf(\线性表已经满了，无法再加入!\ return Null; } else

if( (i<1) ||( i>(p->last+1))) {

printf(\所给插入位置不在有效范围之内!\ return Null; } else {

for(j=L->last;j>=i-1;j--) L->data[j+1]=L->data[j]; L->data[i-1]=x; L->last=L->last+1; }

return (1); }

2. 现要求完成同类型的两个线性表的合并运算，该运算将给定第二个线性表的元素追加到

第一个线性表的最后一个元素之后，假定不会产生因空间不足而上溢的现象，运算完成后应修改第一个线性表的last分量以反映新的表长，运算不破坏第二个线性表。预期的功能用下面的计算示例及算法流程图表示。请将下列给定的算法设计填写完整。 算法功能描述：计算前 L1={1,3,5,7,9}, L2={2,4,6,8}

计算后： L1={1,3,5,7,9,2,4,6,8},L2={2,4,6,8} 线性表的顺序存储结构定义：

#define MaxSize 1024 /*允许的最大数据元素数目*/ typedef int DataType; /*数据元素的类型*/

typedef struct node{

DataType data[MaxSize]; /*存储线性表中数据元素用的数组*/

int last; /*存储表的最后一个元素存放在data数组中的下标号*/

} SequenList;

计算前：

在L1表的存储结构体变量中，

data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9

last=4;

在L2表的存储结构体变量中，计算前：

data[0]=2,data[1]=4,data[2]=6,data[3]=8 last=3

计算后：

在L1表的存储结构体变量中，

data[0]=1,data[1]=3,data[2]=5,data[3]=7,data[4]=9,data[5]=2, data[6]=4,data[7]=6,data[8]=8

last=8;

在L2表的存储结构体变量中，计算前：

data[0]=2,data[1]=4,data[2]=6,data[3]=8 last=3

待完成的算法如下：

void MergeList(SequenList *L1,Sequenlist *L2)

{/*算法进入时：L1指向第一个线性表的结构体变量

L2指向第二个线性表的结构体变量

算法退出后：L1指向第一个线性表的结构体变量，其内容为合并后的表。

L2指向第二个线性表的结构体变量，其内容未变。

*/

int i,j; /*分别表示第一个表及第二个表的当前位置指示器*/ int k; /*循环控制变量*/

int n1,n2; /*分别用于存放表L1及表L2的长度*/ DataType x; /*存放从表L2中读出的数据元素*/ n1=L1->last+1; n2=L2->last+1; i=L1->last+1; j=0;

for(k=0;k< ;k++) {

x= ; L1->data[i]=x; i++; j++; }

=n1+n2-1; return; }

开始 算法流程图：

n1<--表1的长度

n2<--表2的长度

i=表1的最后元 …… 此处隐藏：2004字，全部文档内容请下载后查看。喜欢就下载吧 ……