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

数据结构程序填空题

S设有一个头指针为head的不带头结点单向链表,且p、q是指向链表中结点类型

的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结

点a的数据域相同）,写出相关语句

答案

（1）q->next=head;（2）p=p->next;（3）q->next=p->next;

设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的

指针变量，p指向链表中结点a,（设链表中没有结点的数据域与结点a

的数据域相同）,写出相关语句

答案：（1）q->next=head(2)p=p->next;（3）q->next=p->next

设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的

指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下

程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data

打印出来，并把其中之一从链表中删除，填写程序中的空格。

（1）p=p->next;（2）p->data或prep->data（3）p->next

设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，

并输出链表中各结点中的数据。

答案：（1）&a（2）（3）p->data（4）p=p->next（5）p!=NULL

设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为

head，以下程序的功能是输出链表中各结点中的数据域data。

答案：（1）p->data?（2）p=p->next?（3）p!=NULL?

设线性表为（1，3，7，5），以下程序用说明结构变量的方法建立单向链表，并

输出链表中各结点中的数据。

答：（1）&a?（2）d->next=NULL?（3）p->data?（4）p=p->next?（5）P指向

NULL?

X学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到

n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1]

中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记

录的下标（数组元素的下标）。失败时返回-1，完成程序中的空格。

（1）low<=high（2）mid（3）a[mid].num

Y以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否

则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，

不成功p指向为NULL）答案：（1）NULL（2）k（3）p=p->left（4）p=p->rig

（5）p

以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，

返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不

成功，则p指向为NULL），完成程序中的空格。

（1）p=bt（2）k（3）p=p->left（4）p=p->right

以下程序是折半插入排序的算法=设待排序的记录序列存放在a[1],…a[n]中，

以a[0]作为辅助工作单元，以下程序是要把a[i]插入到已经有序的序列

a[1],…a[i-1]中。

答案：(1)n(2)(s+j)/2;(3)j=m-1;(4)s=m+1;(5)a[k+1]

来源：网络转载

以下函数为直接选择排序算法，对a[1],a[2],?a[n]中的记录进行直接选择排序，

完成程序中的空格

答案：（1）n-1（2）n（3）k=j（4）a[i]=a[k]（5）a[k]=temp

以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针

structnode

答（1）sizeof(structnode)（2）p->next=top（3）top=p

以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找

成功返回该记录的下标，失败时返回-1，完成程序中的空格：

答：（1）low<=high（2）mid（3）a[mid].key

（5）不能，因为不是有序序列，不能用折半查找。

以下程序是快速排序的算法设待序的记录序列存放在a[start],…a[end]中，按记

录的关键字进行快速排序，先进行一次划分，再分别进行递归调用

答：2.(1)i++;(2)i++;(3)a[j]=a[i];(4)j--;(5)(a,i+1,end);

以下程序是折半插入排序的算法（按记录中关键字key排序）设待排序的记录

序列存放在a[1]，…，a[n]中，以a[0]作为辅助工作单元，以下程序是要

把a[i]插入到已经有序的序列a[1]，…，a[i-1]中。

（1）n（2）(s+j)/2（3）j=m-1（4）s=m+1（5）a[k+1]

以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构

中，左、右指针域分别为left和right，数据域data为字符型，BT指向根

结点）。

答案：（1）Postorder(BT->left)（2）

printf("%c",BT->data)

（3）

f,d,e,b,c,a

以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据

域从前向后依次为1,2,3,……,n，完成程序中空格部分。

答案：（1）p（2）q=p（3）(NODE*)malloc(sizeof(NODE))（4）p（5）q=p

以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针

域分别为left和right，数据域data为字符型，BT指向根结点）。

答案：

（1）Inorder(BT->left)（2）printf("%c",BT->data)（3）dbfeac

以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构

中左、右指针域分别为left和right，数据域data为字符型，BT指向根结

点）。

答案：（1）Inorder(BT->left)（2）printf(“%c”,BT->data)（3）Inorder(BT->right)

以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear

分别是链队列的队头、队尾指针

答：（1）malloc(sizeof(structnode))（2）rear->next=p（3）p

以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序

中的空格部分，其中n是元素个数，要求按升序排列。

答：（1）j<=n-1?（2）i<=n-j?（3）a[i]=a[i+1]?（4）a[i+1]=temp?

（5）

4，5，2，1，6，8

来源：网络转载