新疆师范大学计算机科学技术学院 2010—2011学年第一学期期末考试试卷《数据结构》A试卷专业电子 班级08-11 姓名 学号 题号一二三四五六总分分值202020201010100得分一、选择题：(请将正确
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
填入括号中，每题2分共20分）1.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是( )。A.线性结构 B.树型结构 C.图型结构 D.集合2.数组的逻辑结构不同于下列( )的逻辑结构。A.线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
B.栈 C.队列 D.树3.以下数据结构中哪一个是非线性结构？( )。A.队列 B.栈 C.线性表 D.二叉树4.栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素 B.都是先进后出C.都是先进先出 D.没有共同点5.用链接方式存储的队列，在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改6.树最适合用来表示( )。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据7.二叉树的第k层的结点数最多为( )。A．2k-1 B. 2K1 C. 2K-1 D.2k-18.下面程序的时间复杂为( )。for（i=1，s=0；i<=n；i）{ t=1；for(j=1；j<=i；j)t=t*j；s=st；}A.O(n) B.O(n2) C.O(n3) D.O(n4)9.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为( )。A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B.q=p->next；q->data=p->data；p->next=q->next；free(q)；C. q=p->next；p->next=q->next；free(q)；D.q=p->next；p->data=q->data；free(q)；10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 8二、填空题(每小题2分,共20分)1.通常从四个方面评价算法的质量： 、 、______和_________。2.一个算法的时间复杂度为(n3n2log2n14n)/n2，其数量级表示为_____。3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_____个，树的深度为______，树的度为__ __。4.后缀算式923-102/-的值为______。中缀算式（34X）-2Y/3对应的后缀算式为_______________________________。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。6.一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；7.在以HL为表头指针的带表头附加结点的单链表中，判断链表为空的条件为________________。8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。9.用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。10.当栈采用顺序存储结构时，栈顶元素的值可用———————表示；当栈采用链接存储结构时，栈顶元素的值可用_______________表示。三、按题意解答如下问题：(每小题10分,共20分)1、已知稀疏矩阵A如下图所示：1).写出它的三元组线性表；2).给出它的顺序存储表示；3)．给出它的转置矩阵的三元组和顺序存储表示。A=2.什么是结点的度？什么是树的度？四、阅读程序，简述以下算法的功能(每题10分，共20分）1.BT指针指向的一棵二叉树intDepthBTree(BTreeNode*BT){if(BT==NULL)return0; //对于空树，返回0并结束递归else{intdep1=DepthBTree(BT->left); //计算左子树的深度intdep2=DepthBTree(BT->right); //计算右子树的深度if(dep1>dep2) //返回树的深度returndep11;elsereturndep21;}}程序的功能是：2.HQ是链队，则以下程序的功能是：ElemTypeOutQueue(LinkQueue&HQ){if(HQ.front==NULL){ //若链队为空则中止运行cerr<<"链队为空，无法删除!"<
data; //暂存队首元素以便返回sNode*p=HQ.front; //暂存队首指针以便回收队首结点HQ.front=p->next; //使队首指针指向下一个结点if(HQ.front==NULL) //若删除后链队为空，则使队尾指针为空HQ.rear=NULL; deletep; returntemp; }五、程序填空（每题5分，共10分）1.以下程序是向集合中插入一个元素。请在下划线处填上合适的语句或表达式使它完善（10分）。boolInsertSet(sNode*&head,ElemTypeitem){//从单链表中顺序查找是否存在值为item的结点sNode*p= ;while(p!= ){if(p->data==item)break;elsep=p->next;}if(p!=NULL)return ; //插入失败返回假//建立值为item的新结点sNode*tp= ;tp->data=item;//新结点tp插入到单链表的表头tp->next=head;head= ;//返回真表示插入成功returntrue;}2.以下是输出二叉树的算法。请在下划线处填上合适的语句或表达式使它完善（10分）。voidPrintBTree(BTreeNode*BT){ //输出二叉树的广义表表示if(BT!= ){ //树为空时结束递归，否则执行如下操作cout<data; //输出根结点的值if(BT->left!= ||BT->right!= ){cout<<'('; //输出左括号PrintBTree( ); //输出左子树if (BT->right!=NULL)cout<<','; //若右子树不为空则首先输出逗号分隔符PrintBTree( ); //输出右子树cout<<')'; //输出右括号}}}六、编程题(1小题共10分)。1．将一个单链表按逆序链接，即原单链表中存储元素次序为a1,a2…an,则逆序链接后变为an,an-1,…a1.
浙公网安备 33021202002483