国家开放大学(数据结构)章节练习(2020.04.16)

问答题
以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格。
答案：
low<=high；mid；a[mid].key<k；high=mid-1；return-1
单项选择题
数据结构是一门研究计算机中（）对象及其关系的科学。
A.数值运算
B.非数值运算
C.集合
D.非集合
单项选择题
设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收楼顶元素，则出栈操作为（）。
A.x=top->data；top=top->next；
B.top=top->next；x=top->data；
C.x=top->next；top=top->data；
D.top->next=top；x=top->data；
问答题
以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
答案：（1）Inorder（BT->left）；
（2）printf（“%c”，BT->da...
填空题
在一棵树中，每个结点的（）或者说每个结点的（）称为该结点的（），简称为孩子。
答案：子树的根；后继结点；孩子结点
填空题
设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二又树一共有（）个结点。
答案：21
单项选择题
对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（）次元素间的比较。
A.j
B.j-1
C.n-j
D.n-j-1
填空题
设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9，该完全二叉树一共有（）个结点。
答案：18
问答题
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？
答案：出队序列是e2，e4，e3，e6，e5，e1的过程：
（1）e1入栈（栈底到栈顶元素是e1）
（2）...
问答题
以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1，2，3，……，n，完成程序中空格部分。
答案：
（1）p
（2）q=p
（3）（NODE*）malloc（sizeof（NODE））
（4）p
（5）q=p