河南电大数据结构期末复习题1(历年考试题)

1．同一种逻辑结构(B)。A.只能有唯一的存储结构B．可以有不同的存储结构C．只能表示某一种数据元素之间的关系D.以上三种说法均不正确2．链表所具备的特点是(C)。A可以随机访问任一结点B占用连续的存储空间C插入删除元素的操作不需要移动元素结点D可以通过下标对链表进行直接访问3．数据的物理结构(D)。A与数据的逻辑结构无关B仅仅包括数据元素的表示C只包括数据元素间关系的表示n包括数据元素的表示和关系的表示4.线性结构中数据元素的位置之间存在(A)的关系。A-对一B一对多C多对多D.每一个元素都有一个直接前驱和一个直接后继5.以下表中可以随机访问的是：（D）。A.单向链表B.双向链表C.单向循环链表D.顺序表6.算法的时间复杂度与（C）有关。A.所使用的计算机B.与计算机的操作系统C.与算法本身D.与数据结构7.设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（B）。A.n-i+1B.n-iC.n-i-1D.i8.在一个单链表中，p、q分别指向表中两个相邻的结点：且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句是（C）。A.p=q-nextB.p-next=qC.p-next=q-nextD.q-next=NULL9.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删除结点的值，则执行（A）。A.x=top-data;top=top-next;B.x=top-data;C.top=top-next;x=top-data;D.top=top-next;x=data;10.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C）。A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是(A)(进栈出栈可以交替进行)。A.dccabB.edcbaC.decbaD.abcde12.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（B）。A.26/10B.29/10C.29/9D.31/1013.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排列序列的正确位置的方法是（C）。A.冒泡B.直接插入C.折半插入D.选择排序14.设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始），则矩阵中元素氏，。在一维数组B中的下标是(A)A．33B．32C．85D．4115．在一个无向图中，所有顶点的度数之和等于边数的(D)倍。A.3B.2.5C.1.5D．2二、填空题（每小题2分，共24分）16.栈和队列的操作特点分别是后进先出和先进先出。17.结构中的数据元素存在多对多的关系称为图状（网状）结构。18.根据数据元素间关系的不同特性，通常可分为集合、线性、树形、图状、四类基本结构。19.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-1和O(n)。20.在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next和p-next=s;的操作。21．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、左指针、右指针。22．-棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左右孩子的编号分别为2i、2i+1。23．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h和h=s。24.在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r-next=s和r=s；(结点的指针域为next)。25.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有12个结点。（根所在结点为第1层）26.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和非零元素值三项信息。27.在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较3次。三、综合题（每小题10分，共30分）28．(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权），给出相应权重值叶结点的哈夫曼编码。解：2：11103：11114：1107：008：019：10(2)-棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由。解：2n-1个，因为非叶结点数比叶结点数少一个。29．一组记录的关键字序列为(46，79，56，38，40，84)(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）。解：（1）初始序列46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，84(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。解：30．设查找表为(50，60，75，85，96，98，105，110，120，130)(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？解：3次(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？解：4次(3)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点）。解：四、程序填空题（每空2分，共16分）31.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前依次为1，2，3，…，n,完成程序中空格部分。NODE*create(n){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=(1)p;(2)q=p;p-next=NULL;/*建立头结点*/for(i=1;i=n;i++){p=(3)(NODE*)malloc(sizeof(NODE));p-data=i;p-next=NULL;q-next=(4)p;(5)q=p;}return(head);}32.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左，右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidInorder(structBTreeNode*BT){if(BT!=NULL){(1)Inorder(BT-left);(2)printf(“%c”,BT-data);(3)Inorder(BT-right);}}