注意：此页面搜索的是所有试题
数据结构国家开放大学
.一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）。
单选题 (2 分) 2分
A.
16，25，35，48，23，40，79，82，36，72
B.
16，25，35，48，79，82，23，36，40，72
C.
16，25，48，35，79，82，23，36，40，72
D.
16，25，35，48，79，23，36，40，82，72
已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（ ）。
单选题 (2 分) 2分
A.
16，28，34，54，73，62，60，26，43，95
B.
28，16，34，54，62，73，60，26，43，95
C.
28，16，34，54，62，60，73，26，43，95
D.
16，28，34，54，62，60，73，26，43，95
一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
单选题 (2 分) 2分
A.
40，38，46，79，56，84
B.
40，38，46，56，79，84
C.
40，38，46，84，56，79
D.
38，40，46，56，79，84
一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。
单选题 (2 分) 2分
A.
39，46，41，57，80，47
B.
39，47，46，80，41，57
C.
41，39，46，47，57，80
D.
39，80，46，47，41，57
设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。
#define NULL 0
void main( )
{ NODE *head ,*p ;
p=head; /*p为工作指针*/
do
{printf(“%d\n”, __(1)__;
__(2)__;
}while__(3)__;
}
匹配题 (6 分) 6分 (计分规则:按匹配正确项计分)
设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句
(1)使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱
q=p; x=p->data;
while __(1)__）q=q->next;
q->next=head;
q=p; p=p->next;
while(p->data!=x)
{ q=p;
__(2)__
}
s->next=p;
__(3)__
以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc __(1)__;
p->data=x;
__(2)__;
__(3)__;
}
以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别链队列的队头、队尾指针
struct node
{ ElemType data;
struct node *next;
};
struct node *front，*rear;
void InQueue(ElemType x)
{
struct node *p;
p= (struct node*) malloc __(1)__;
p->data=x;
p->next=NULL;
__(2)__;
rear= __(3)__;
以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。完成程序中空格部分。
void
Inorder (struct BTreeNode *BT)
{
if( BT!=NULL)
{
Inorder(BT->left);
__(1)__
__(2)__
}
利用上述程序对左图进行后序遍历，结果是__(3)__;
1）以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。该树的带权路径长度为 .
A,64 B.65 C. 62 D. 66
权重为3的叶结点的哈夫曼编码为 。
A.010 B.0101 C.000 D.0111
（1）以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，该树的带权路径长度为 1
A,66 B. 80 C. 62 D. 87
权重值为4的叶结点的哈夫曼编码为 2 。
A.0001 B. 1110 C.001 D. 110
已知某二叉树的后序遍历序列是 debca，中序遍历序列是 dbeac，该二叉树的根结点是(
A.e
B.C
C.b
D.a
先序遍历序列是 。
A. e,b,c,d,a B. c,a,b,,d,e C. a,b,d,e,c D. a.c,b,d,e
单选题 (2 分) 2分
A.
16，25，35，48，23，40，79，82，36，72
B.
16，25，35，48，79，82，23，36，40，72
C.
16，25，48，35，79，82，23，36，40，72
D.
16，25，35，48，79，23，36，40，82，72
已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（ ）。
单选题 (2 分) 2分
A.
16，28，34，54，73，62，60，26，43，95
B.
28，16，34，54，62，73，60，26，43，95
C.
28，16，34，54，62，60，73，26，43，95
D.
16，28，34，54，62，60，73，26，43，95
一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
单选题 (2 分) 2分
A.
40，38，46，79，56，84
B.
40，38，46，56，79，84
C.
40，38，46，84，56，79
D.
38，40，46，56，79，84
一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。
单选题 (2 分) 2分
A.
39，46，41，57，80，47
B.
39，47，46，80，41，57
C.
41，39，46，47，57，80
D.
39，80，46，47，41，57
设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。
#define NULL 0
void main( )
{ NODE *head ,*p ;
p=head; /*p为工作指针*/
do
{printf(“%d\n”, __(1)__;
__(2)__;
}while__(3)__;
}
匹配题 (6 分) 6分 (计分规则:按匹配正确项计分)
设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句
(1)使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱
q=p; x=p->data;
while __(1)__）q=q->next;
q->next=head;
q=p; p=p->next;
while(p->data!=x)
{ q=p;
__(2)__
}
s->next=p;
__(3)__
以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc __(1)__;
p->data=x;
__(2)__;
__(3)__;
}
以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别链队列的队头、队尾指针
struct node
{ ElemType data;
struct node *next;
};
struct node *front，*rear;
void InQueue(ElemType x)
{
struct node *p;
p= (struct node*) malloc __(1)__;
p->data=x;
p->next=NULL;
__(2)__;
rear= __(3)__;
以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。完成程序中空格部分。
void
Inorder (struct BTreeNode *BT)
{
if( BT!=NULL)
{
Inorder(BT->left);
__(1)__
__(2)__
}
利用上述程序对左图进行后序遍历，结果是__(3)__;
1）以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。该树的带权路径长度为 .
A,64 B.65 C. 62 D. 66
权重为3的叶结点的哈夫曼编码为 。
A.010 B.0101 C.000 D.0111
（1）以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，该树的带权路径长度为 1
A,66 B. 80 C. 62 D. 87
权重值为4的叶结点的哈夫曼编码为 2 。
A.0001 B. 1110 C.001 D. 110
已知某二叉树的后序遍历序列是 debca，中序遍历序列是 dbeac，该二叉树的根结点是(
A.e
B.C
C.b
D.a
先序遍历序列是 。
A. e,b,c,d,a B. c,a,b,,d,e C. a,b,d,e,c D. a.c,b,d,e