试卷代号：1010 座位号■■ 中央广播电视大学2007一2008学年度第一学期“开放本科”期末考试 计算机专业数据结构 试题 2008年1月 题号 二 三 四 五 六 总 分 分数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1,下面程序段的时间复杂度为( for(int i=0;i<m;i++) for(int j=0;j<n;j++)a[i]]=i*j; A.O(m2) B.O(n2) C.O(m关n) D.O(m十n) 2.在二维数组中，每个数组元素同时处于( )个向量中。 A.0 B.1 C.2 D.n 3.设有两个串1和P,求p在1中首次出现的位置的运算叫做( )。 A.求子串 B.模式匹配 C.串替换 D.串连接 4.利用双向链表作线性表的存储结构的优点是()。 A.便于单向进行插入和删除的操作 B.便于双向进行插人和剔除的操作 C.节省空间 D.便于销毁结构释放空间 68
试卷代号 :1010 座位号巨口 中央广播电视大学2007-2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题 zoos年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号(每小题 2分，共 18分) 1.下面程序段的时间复杂度为( )。 for(int i=0; i<m; i十 十) for(intj=0;J<n; J++) a[i][j]=i*J; A. O ( m2) B. O ( nZ) C. 0(m *n) D. 0(m十n) 2.在二维数组中，每个数组元素同时处于( )个向量中。 A. 0 B. 1 C. 2 D. n 3.设有两个串 t和 U，求 p在 ，中首次出现的位置的运算叫做( A.求子串 I3.模式匹配 C.串替换 D.串连接 4.利用双向链表作线性表的存储结构的优点是( )。 .便于单向进行插入和删除的操作 便于双向进行插人和删除的操作 节省空间 便于销毁结构释放空间
5.设链式栈中结点的结构为(data,1ink),且top是指向栈顶的指针。若想在链式栈的栈 顶插人一个由指针s所指的结点，则应执行()操作。 A.top->link=s; B.s->link=top->link;top->link=s; C.s->link=top;top=s; D.s->link=top;top=top->link; 6.一棵具有35个结点的完全二叉树的高度为()。假定空树的高度为一1。 A.5 B.6 C.7 D.8 7.向具有n个结点的堆中插人一个新元素的时间复杂度为()。 A.0(1) B.O(n) C.O(log2n) D.O(nlogzn) 8.在一棵AVL树中，每个结点的平衡因子的取值范围是( ）. A.-1~1 B.-22 C.1-2 D.01 9.一个有n个顶点和n条边的无向图一定是()的。 A.连通 B.不连通 C.无回路 D.有回路 得 分 评卷人 二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1.数据结构包括 、存储结构和对数据的运算这三个方面。 2.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 存取的。 3.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一 维数组需要至少具有 个元素。 4.对于一棵具有个结点的树，该树中所有结点的度数之和为 5.在一棵高度为3的理想平衡二叉树中，最少含有 个结点，假定树根结点的高 度为0。 6.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为 个。 7.用邻接矩阵存储图，占用的存储空间与图中的 数有关。 69
5.设链式栈中结点的结构为(data } link)，且 top是指向栈顶的指针。若想在链式栈的栈 顶插人一个由指针 s所指的结点，则应执行( )操作。 A. top一>link=s; B. s一>link=top一>link;top一>link=s; C. s一>link=top;top=s; D. s一>link二top;top=top一>link; 6.一棵具有 35个结点的完全二叉树的高度为( )。假定空树的高度为一to A.5 B.6 C. 7 D. 8 7.向具有 n个结点的堆中插 人一个新元素的时间复杂度为( )。 A. O (1) B. 0(n) C. O(log2 n) D. O(nlogZ n) 8.在一棵 AVL树中，每个结点的平衡因子的取值范围是( )。 A.一1 ^-1 13，一2一2 C. 1一 2 D. 0 }-1 9.一个有 n个顶点和 n条边的无 向图一定是( )的 。 A.连通 B.不连通 C.无回路 D.有 回路 得 分 评卷人 二、填空题，在横线处填写合适的内容(每小题 2分，共 14分) 1.数据结构包括 、存储结构和对数据的运算这三个方面。 2.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 存取的。 3.将一个 n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中.则该一 维数组需要至少具有 个元素。 4.对于一棵具有n个结点的树，该树中所有结点的度数之和为_ 。 5.在一棵高度为3的理想平衡二叉树中，最少含有_ _ _个结点，假定树根结点的高 度为 Oa 6.假定对长度I7 = J。的有序表进行折半搜索，则对应的判定树中最底层的结点数为 个 。 7.用邻接矩阵存储图，占用的存储空间与图中的_ _数有关。 69
得分 评卷人 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小 题2分，共14分) )1.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 )2.用字符数组存储长度为n的字符串，数组长度至少为n十1。 )3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 )4.邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。 ( )5.对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的新所有顶点。 )6.在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 ( )7.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 得 分 评卷人 四、运算题（每小题6分，共30分） 1.假定一棵二叉树广义表表示为a(b(c),d(e,f),分别写出对它进行中序、后序、按层遍 历的结果。 中序： 后序： 按层： 2.一个一维数组a[12]中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据 折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成 功搜索时的平均搜索长度。 度为1的结点个数： 平均搜索长度： 3.假定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列中元素的 排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空 的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点： 70
得 分 评卷人 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小 题 2分 ，共 14分) )1 )2 2 .、 了 ‘ 龟 0 口 ‘斗 、.产 、 J )5 )6 ( )7 算法和程序都应具有下面一些特征 :有输人 ，有输 出，确定性，有穷性 ，有效性 。 用字符数组存储长度为 n的字符串，数组长度至少为 n-1- l o 在用循环单链表表示的链式队列中，可以不设队头指针 ，仅在链尾设置队尾指针 。 邻接矩阵适用于稀疏图的表示 ，邻接表适用于稠密图的表示。 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索 ，不可以采用折半搜索 。 图中各个顶点 的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 得 分 评卷人 四、运算题(每小题 6分.共 30分 ) 1.假定一棵二叉树广义表表示为 a(b(c),d(e,f))，分别写出对它进行中序、后序、按层遍 历的结果。 中序 : 后序 : 按层 : 2.一个一维数组 a巨12]中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据 折半搜索所对应的判定树 ，写出该判定树 中度为 1的结点个数 ，并求 出在等概率情况下进行成 功搜索时的平均搜索长度。 度为 1的结点个数: 平均搜索长度: 3.f段定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列 中元素的 排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空 的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点 : 右子树为空的所有一单支结点 : 所有叶子结点 :
4.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5,6}; E={,,,,,,,, ,1: 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出： (])从顶点】出发进行深度优先搜索所得到的顶点序列； (2)从顶点1出发进行广度优先搜索所得到的顶点序列。 (1): (2): 5.已知一个数据序列为{16,45,27,23,41,15,56,64}，请把它调整为一个最大堆。 最大堆： 得分 评卷人 五、算法分析题（每小题6分，共12分） 1.下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅 读算法，在划有横线的上面填写合适的内容。 ListNode Mergel(ListNode *pl,ListNode *p2) { ListNode p=new ListNode,f=p; while(pl！=NULL&&.p2！=NULL) if(pl->datadata)( p->link=pl; else (p->link=p2;p2=p2->link; if(pl!=NULL)p->link=pl;else p->link=p2; pl=p2=NULL; return f->link; 71
4甲已知一个图的顶点集 V和边集 G分别为: V={1，2，3,4，5，6}; E_{，，，，，，E4，6>，， ，}; 假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出: (1)从顶点 1出发进行深度优先搜索所得到的顶点序列; (2)从顶点 1出发进行广度优先搜索所得到的顶点序列。 (1): (2): 5二已知一个数据序列为{16,45,27,23,41,15,56,64}，请把它调整为一个最大堆。 最大堆: 得 分 评卷人 五、算法分析题(每小题 6分，共 12分) 1.下面算法的功能为:将两个有序单链表合并成一个有序单链表并返回其表头指针。阅 读算法，在划有横线的上面填写合适的内容。 ListNode*Mergel ( ListNode*apl，ListNode 邑p2) ListNode * p=new ListNode, while(pl!=NULL&&p2! { *f=p; = NULL) if(pl一>datadata) P一>link=pl; ) else { p一>link= p2;p2=p2一>link;} ) if(pl!=NULL.) p一>link二p1;else p一>link二p2; p1=p2“NULI.; ret urn f一>link;
2.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法 的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode BTreeSwopX(BinTreeNode BT) if(BT==NULL)return NULL: else BinTreeNode pt=new BinTreeNode; pt->data=BT->>data; pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } } 算法功能： 得 分 评卷人 六、算法设计题（每小题6分，共12分】 1.已知f为单链表的表头指针，单链表中的结点结构为(data,limk),并假定每个结点的 值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若 单链表为空则返回数值0。 int Max(LinkNode f); 2.设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明 写出从此队列中别除一个元素的算法。 //循环队列定义 struct CyclicQueue ElemType elem[M]; /M为已定义过的整型常量 int rear; /rear指向队尾元素的后一个位置 int length; //八ength指示队列中元素个数 }; /若队列非空则删除队头元素并由引用参数x带回，同时返回true;否则若队列为空则返 ▣false。 bool DelCQueue(CyclicQueue&.Q,ElemType&x); 72
2.已知二叉树中的结点类型 BinTreeNode定义为: struct BinTreeNode{ElemType data;BinTreeNode‘left，‘right;}; 其中 data为结点值域，left和 right分别为指向左、右子女结点的指针域。根据下面算法 的定义指出其功能。算法中参数 BT指向一棵二叉树。 BinTreeNode‘ BTreeSwopXdata=BT一>data; pt一>right=BTreeSwopX(BT一>left); pt一>left= BTreeSwopX( BT一>right); return pt; } } 算法功能 : 得 分 评卷人 六、算法设计题(每小题 6分 ，共 12分 ) 1.已知f为单链表的表头指针，单链表中的结点结构为(data, link)，并假定每个结点的 值均为大于 。的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若 单链表为空则返回数值 。。 intMax(LinkNode }- f}; 2.设 Q是一个由其队尾指针和队列长度标识的循环队列 ，按照下面队列定义和函数声 明 写出从此队列中删除一个元素的算法 。 //循环队列定义 struct. CyclicQueue { Elem"Type elem仁M]; tnt rear; int length; //M为已定义过的整型常量 //rear指向队尾元素的后一个位置 //length指示队列中元素个数 }; /若队列非空则删除队头元素并由引用参数 x带回，同时返回true;否则若队列为空则返 回 falseo bool DelCQueue(CyclicQueue}- Q，ElemType}. x);
试卷代号：1010 中央广播电视大学2007一2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2008年1月 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分】 1.C 2.C 3.B 4.B 5.C 6.A 7.C 8.A 9.D 二、填空题，在横线处填写合适内容（每小题2分，共14分）】 1.逻辑结构 2.下标（或顺序号） 3.n(n+1)/2 4.n-1 5.8 6.19 7.顶点 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1.错 2.对 3.对 4.错 5.对 6.错 7.对 四、运算题（每小题6分，共30分） 1.中序：c,b,a,e,d,f //2分 后序：c,b,e,f,d,a 1/2分 按层：a,b,d,c,e,f 112分 2.度为1的结点个数：5 /13分 平均搜索长度：37/12 113分 3.左子树为空的所有单支结点：15,23,42,44 /12分 右子树为空的所有单支结点：30 /12分 所有叶子结点：26,48,74 /2分 4.(1)1,2,4,5,3,6 //3分 (2)1,2,3,4,5,6 /13分 5.最大堆：{64,45,56,23,41,15,27,16} 五、算法分析题（每小题6分，共12分） 1.pl=pl->link,p=p->link //每空3分 2.生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右 子树（或左、右孩子的值）交换的结果。 73
试卷代号:1010 中央广播电视大学2007-2008学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2008年 1月 一、单项选择题 ，在括号内填写所选择的标号(每小题·2分，共 18分) 1. C 6. A 2. C 3.B 4. B 5.C 7. C 8. A 9. D 二、填空题 。在横线处填写合适内容(每小题 2分 ，共 14分) 1.逻辑结构 5.8 2.下标(或顺序号) 6. 19 3. n(n-F-1)/2 7，顶 点 4. n一 1 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小题2分，共14分) 1.错 2.对 3.对 4.错 5.对 6.错 7.对 四、运算题 (每小题 6分，共 30分) 1.中序 :c,b,a,e,d,f //2分 后序 ;c,b,e,f,d,a //2分 按层 :a,b,d,c,e,f //2分 2.度为 1的结点个数 :5 //3分 平均搜索长度:37/12 //3分 3.左子树为空的所有单支结点:15,23,42,44 //2分 右子树为空的所有单支结点:30 //2分 所有叶子结点 :26,48,74 //2分 4.(1)1，2，4，J，3，G //3分 (2) 1,2，3，4，5，6 //3分 5.最大堆 :{64,45,56,23,41,15,27,16} 五、算法分析题 (每小题 6分 ，共 12分) l, pl=pl一>link,p= }。一、link //每空 3分 2.生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树 13"I}中所有结点的左、右 子树(或左 、右孩子的值)交换的结果。 7;3
六、算法设计题（每小题6分，共12分） 1.评分标准：按注释酌情给分。 int Max(LinkNode *f) { if(f==NULL)return 0; /11分 if(f->link==NULL)return f->data; /12分 int temp=Max(f->>link); 114分 if(f->data>temp)return f->data; /15分 else return temp; /16分 2.评分标准：按注释酌情给分。 bool DelCQueue(CyelicQueue&.Q,ElemType&.x) if(Q.length==0)return false; /11分 x=Q.elem[(Q.rear-Q.length+M)%M]; 1/4分 Q.length--; /5分 return true; /16分 74
六、算法设计题 (每小题 6分 ，共 12分) 1.评分标准:按注释酌情给分。 int Max(LinkNode*f) if(f==NULL) return 0; iflink= =NULL) return f一> data ; int temp=Max(f一>link); if(f一>data> temp) return f一>data; else return temp; 刀1分 /2分 刀4分 /l5分 //6分 } 2.评分标准:按注释酌情给分。 bool DelCQueue(CyclicQueue乙Q, ElemType乙x) { if(Q. length二=0)return false; x= Q, elem[ ( Q. rear一Q. length-I- M) 0 o M] Q. length一一; return true; //1分 刀4分 // 分 //6分 74