2007-2008第一学期数据结构期末试卷A答案
- 格式：doc
- 大小：117.50 KB
- 文档页数：6
g
v
n
m d
(b)
b b v (a)
i d a
c
c d (d)
(c)
3) abd 4) bcd
a b
is(are) the complete trees(完全二叉树) is(are) the full trees(满二叉树).
z c x (b)
g
d
e
(a)
v
第 1 页 共 6 页
(c)
(d)
2. fig.1 is an example binary tree. Node gde__________are leaves(叶子). The depth(深度) of e is 2________. The height of this tree is(这 a 棵树的高度是)3___. 3. the number of empty subtrees in a non-empty binary tree is _one_______ more than the number of nodes in the tree.
2分
第 6 页 共 6 页来自信息工程学院一 18 二 32 三 16
考生注意事项：1、本试卷共 页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、 填空题(每空 2 分，共 18 分)
得分 评阅人
1.according the following figures, 1) ab is(are) the tree data structures.(树形结构) 2) c is(are) linear data structures(线性结构)
#include <malloc.h> #include <stdio.h> typedef struct node { char data; struct node *lchild,*rchild; }TREENODE; A struct node *creat_tree() { TREENODE *t; char c; scanf("%c",&c); if(c=='#') return(NULL); else {t=(TREENODE *)malloc(sizeof(TREENODE)); t->data=c; t->lchild=creat_tree(); t->rchild=creat_tree(); } return(t); } 6分 TREENODE * find(char x, TREENODE T) { if (T==NULL) return(NULL);
第 4 页 共 6 页
2分
for(j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j]; 2 分 L.data[i-1]=x; L.length++; return L; 3分 }
seqlist sqinv(seqlist L) {int i,t; for(i=0;i<=(L.length-1)/2;i++) {t=L.data[i]; L.data[i]=L.data[L.length-1-i]; L.data[L.length-1-i]=t;} return(L);}
四.程序设计(共 34 分)
得分 评阅人
1. write a c implementation which can complete the following task: first insert element x at the ith position of the the Array-based list. (在第 i 个位 置上上插入元素)（14 分） seqlist sqinsert(seqlist L,int i,int x) then inverse the elements of array.(将数组中的元素逆置) seqlist sqinv(seqlist L) typedef struct {int data[maxsize]; int length; }seqlist; seqlist sqinsert(seqlist L,int i,int x) { int j; if(L.length==maxsize) {printf("overflow");exit(0);} if(i<1|| i>L.length+1) {printf("position error\n");exit(0);}
南昌大学 2007～2008 学年第一学期期末考试试卷
试卷编号： 课程编号： X61010508 课程名称： 适用班级： 自动化 05 级 学院：
题号 题分 得分
( A)卷 闭卷
数据结构 学号： 自动化
六 七 八
考试形式：
姓名： 专业：
四 34 五
班级： 考试日期：
九 十 总分 100 累分人 签名
3分
4分
2. write a implementation to complete the following task. the main function are needed to write（20 分） 1)write a function named TREENODE *creat_tree( ) to building the binary search tree (the node value is input from thekeyboard. ‘#’ means the empty node.), and the write the character you input from the keyboard(写出一个子函数 TREENODE *creat_tree( )来建立下面这棵二 叉查找树，结点的值从键盘上输入,#表示空结点,并写出应从键盘上输入的 字符。) 2)write a function TREENODE * find(char x, TREENODE T), to find the x in the tree.(写出一个子函数 TREENODE * find(char x, TREENODE T) 在树中查 找结点 x.) 3)write the main program.(写出主程序)
typedef struct {int data[MAXSIZE]; int front, rear; }sequeue;
int squepop(sequeue *Qp) { int j; if (Qp->front==Qp->rear) {printf("empty");exit(0);} Qp->front=(Qp->front+1)%MAXSIZE; j=Qp->data[Qp->front]; return j;}
7 2 5 37
42
42
40
4. build the Huffman tree for the message “CAASTTATASA” and determine the Huffman codes.(8’)有一段电文“CAASTTATASA” ，试设 计赫夫曼编码（画出构造的赫夫曼树） 11
c: 1 s:2 T: 3 a:5
1
5
0 0 3
6 1 0 3 1 1 2
A: 0 T: 10 C: 110 S: 111
三.程序填空
得分
(每空 2 分,共 16 分)
c
评阅人
a) finish the Bubble Sort implementation.
void sortbub(int a[], int n) { int j,i,tmp; for(i=0;i<n-1;i++) {for(j=n-1;j>i;j--) if(a[j]<a[j-1]) {tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; } } typedef struct { int data[MAXSIZE];
B C F E
G H
第 2 页 共 6 页
3. if values are inserted in the order 42,42, 7, 2, 5, 37,40. draw the Binary Search Trees for the collection of values. (8’) (依次插入结点 42,42, 7, 2, 5, 37, 40,画出所形成的二叉查找树)
第 5 页 共 6 页
E
B
F D
2分
if (x<T->data) return( find(x,T->lchild)); else if(x>T->data) return( find(x,T->rchild)); else return(T);} 6 分 main() {TREENODE *root,*p; char x='d'; root=creat_tree(); t=find(x,root); if(t==NULL) printf(“not found the node\n”); } 4分 输入:EBA##D##F##
g b c
d
4. the ____stack______ is a list-like structure in which elements may be inserted or removed from only one end.
二、简答题（共 32 分） 得分 评阅人
e
1．Determine O(.) for the following code fragments in the worst case.(计算时 间复杂度)。(8’) （a）For(i=0;i<N;i++) A[i]=0; For(i=0;i<N;i++) for(j=0;j<i;j++) A[i]+= A[j]+i+j; c O(n2) 2) s=0; for(j=1;j<=n;j*=2) for(k=1;k<n;k++) s++; O(nlog 2 n) 2.The preorder enumeration for the binary tree (一棵二叉树的先序遍历 是)is ABCFGHE, And the inorder enumeration for the tree is(它的中序 遍历是) CBAGHFE. Draw the tree and the postorder enumeration for the tree is_______CBHGEFA_______.(8’)(画出这棵树并写出它的后序 A 遍历)
v
n
m d
(b)
b b v (a)
i d a
c
c d (d)
(c)
3) abd 4) bcd
a b
is(are) the complete trees(完全二叉树) is(are) the full trees(满二叉树).
z c x (b)
g
d
e
(a)
v
第 1 页 共 6 页
(c)
(d)
2. fig.1 is an example binary tree. Node gde__________are leaves(叶子). The depth(深度) of e is 2________. The height of this tree is(这 a 棵树的高度是)3___. 3. the number of empty subtrees in a non-empty binary tree is _one_______ more than the number of nodes in the tree.
2分
第 6 页 共 6 页来自信息工程学院一 18 二 32 三 16
考生注意事项：1、本试卷共 页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、 填空题(每空 2 分，共 18 分)
得分 评阅人
1.according the following figures, 1) ab is(are) the tree data structures.(树形结构) 2) c is(are) linear data structures(线性结构)
#include <malloc.h> #include <stdio.h> typedef struct node { char data; struct node *lchild,*rchild; }TREENODE; A struct node *creat_tree() { TREENODE *t; char c; scanf("%c",&c); if(c=='#') return(NULL); else {t=(TREENODE *)malloc(sizeof(TREENODE)); t->data=c; t->lchild=creat_tree(); t->rchild=creat_tree(); } return(t); } 6分 TREENODE * find(char x, TREENODE T) { if (T==NULL) return(NULL);
第 4 页 共 6 页
2分
for(j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j]; 2 分 L.data[i-1]=x; L.length++; return L; 3分 }
seqlist sqinv(seqlist L) {int i,t; for(i=0;i<=(L.length-1)/2;i++) {t=L.data[i]; L.data[i]=L.data[L.length-1-i]; L.data[L.length-1-i]=t;} return(L);}
四.程序设计(共 34 分)
得分 评阅人
1. write a c implementation which can complete the following task: first insert element x at the ith position of the the Array-based list. (在第 i 个位 置上上插入元素)（14 分） seqlist sqinsert(seqlist L,int i,int x) then inverse the elements of array.(将数组中的元素逆置) seqlist sqinv(seqlist L) typedef struct {int data[maxsize]; int length; }seqlist; seqlist sqinsert(seqlist L,int i,int x) { int j; if(L.length==maxsize) {printf("overflow");exit(0);} if(i<1|| i>L.length+1) {printf("position error\n");exit(0);}
南昌大学 2007～2008 学年第一学期期末考试试卷
试卷编号： 课程编号： X61010508 课程名称： 适用班级： 自动化 05 级 学院：
题号 题分 得分
( A)卷 闭卷
数据结构 学号： 自动化
六 七 八
考试形式：
姓名： 专业：
四 34 五
班级： 考试日期：
九 十 总分 100 累分人 签名
3分
4分
2. write a implementation to complete the following task. the main function are needed to write（20 分） 1)write a function named TREENODE *creat_tree( ) to building the binary search tree (the node value is input from thekeyboard. ‘#’ means the empty node.), and the write the character you input from the keyboard(写出一个子函数 TREENODE *creat_tree( )来建立下面这棵二 叉查找树，结点的值从键盘上输入,#表示空结点,并写出应从键盘上输入的 字符。) 2)write a function TREENODE * find(char x, TREENODE T), to find the x in the tree.(写出一个子函数 TREENODE * find(char x, TREENODE T) 在树中查 找结点 x.) 3)write the main program.(写出主程序)
typedef struct {int data[MAXSIZE]; int front, rear; }sequeue;
int squepop(sequeue *Qp) { int j; if (Qp->front==Qp->rear) {printf("empty");exit(0);} Qp->front=(Qp->front+1)%MAXSIZE; j=Qp->data[Qp->front]; return j;}
7 2 5 37
42
42
40
4. build the Huffman tree for the message “CAASTTATASA” and determine the Huffman codes.(8’)有一段电文“CAASTTATASA” ，试设 计赫夫曼编码（画出构造的赫夫曼树） 11
c: 1 s:2 T: 3 a:5
1
5
0 0 3
6 1 0 3 1 1 2
A: 0 T: 10 C: 110 S: 111
三.程序填空
得分
(每空 2 分,共 16 分)
c
评阅人
a) finish the Bubble Sort implementation.
void sortbub(int a[], int n) { int j,i,tmp; for(i=0;i<n-1;i++) {for(j=n-1;j>i;j--) if(a[j]<a[j-1]) {tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; } } typedef struct { int data[MAXSIZE];
B C F E
G H
第 2 页 共 6 页
3. if values are inserted in the order 42,42, 7, 2, 5, 37,40. draw the Binary Search Trees for the collection of values. (8’) (依次插入结点 42,42, 7, 2, 5, 37, 40,画出所形成的二叉查找树)
第 5 页 共 6 页
E
B
F D
2分
if (x<T->data) return( find(x,T->lchild)); else if(x>T->data) return( find(x,T->rchild)); else return(T);} 6 分 main() {TREENODE *root,*p; char x='d'; root=creat_tree(); t=find(x,root); if(t==NULL) printf(“not found the node\n”); } 4分 输入:EBA##D##F##
g b c
d
4. the ____stack______ is a list-like structure in which elements may be inserted or removed from only one end.
二、简答题（共 32 分） 得分 评阅人
e
1．Determine O(.) for the following code fragments in the worst case.(计算时 间复杂度)。(8’) （a）For(i=0;i<N;i++) A[i]=0; For(i=0;i<N;i++) for(j=0;j<i;j++) A[i]+= A[j]+i+j; c O(n2) 2) s=0; for(j=1;j<=n;j*=2) for(k=1;k<n;k++) s++; O(nlog 2 n) 2.The preorder enumeration for the binary tree (一棵二叉树的先序遍历 是)is ABCFGHE, And the inorder enumeration for the tree is(它的中序 遍历是) CBAGHFE. Draw the tree and the postorder enumeration for the tree is_______CBHGEFA_______.(8’)(画出这棵树并写出它的后序 A 遍历)
