北師大數(shù)據(jù)結構在線作業(yè)

1、1/順序存儲結構中數(shù)據(jù)元素之間的邏輯關系是由（ ）表示的。線性結構非線性結構存儲位置指針2/算法指的是（ ）。對特定問題求解步驟的一種描述，是指令的有限序列。計算機程序解決問題的計算方法數(shù)據(jù)處理3/算法在發(fā)生非法操作時可以作出處理的特性稱為（ ）。健壯性確定性可行性正確性4/若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節(jié)省時間。順序表單鏈表雙鏈表單循環(huán)鏈表5/頭結點的單鏈表head為空的判定條件是（ ）。head=NULLhead->next=NULLhead->next=headhead!=NULL6/單循環(huán)鏈表的主要優(yōu)點是（ ）。不再需要

2、頭指針了從表中任一結點出發(fā)都能掃描到整個鏈表；已知某個結點的位置后，能夠容易找到它的直接前趨；在進行插入、刪除操作時，能更好地保證鏈表不斷開。7/使用雙向鏈表存儲線性表，其優(yōu)點是可以（ ）。方便雙向查找更方便數(shù)據(jù)的插入和刪除節(jié)約存儲空間很快回收存儲空間8/設數(shù)組Sn作為兩個棧S1和S2的存儲空間，對任何一個棧只有當Sn全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（ ）。S1的棧底位置為0，S2的棧底位置為n-1S1的棧底位置為0，S2的棧底位置為n/2S1的棧底位置為0，S2的棧底位置為nS1的棧底位置為0，S2的棧底位置為19/設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、

3、e4、e5、e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應該是（ ）。643210/表達式a*(b+c)-d的后綴表達式是（ ）。abcd*+-abc+*d-abc*+d-+*abcd11/深度為k的完全二叉樹至少有（）個結點。2k-2+12k-12k-12k1-112/一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有（）成立。n=h+mh+m=2nm=h-1n=2h-113/設森林中有4棵樹，樹中結點的個數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，根結點的左子樹上有（）個結點。n1-1n1n1

4、+n2+n3n2+n3+n414/有一個按元素值排好序的順序表（長度大于2），分別用順序查找和折半查找與給定值相等的元素，比較次數(shù)分別是s和b，在查找不成功的情況下，s和b的關系是（ ）。s=bs>bs不一定15/散列技術中的沖突指的是（ ）。兩個元素具有相同的序號兩個元素的鍵值不同，而其他屬性相同數(shù)據(jù)元素過多不同鍵值的元素對應于相同的存儲地址簡答帶頭結點的鏈表和不帶頭結點的鏈表有什么不同？單鏈表是一種最為基本的數(shù)據(jù)結構，常用的單鏈表又分為帶頭結點和不帶頭結點兩種。從線性表的定義可以知道，線性表要求允許在任意位置進行插入和刪除操作。所有的鏈表都有一個頭指針head， 帶頭結點的鏈表中he

5、ad的數(shù)據(jù)項為空 。具體分析。1.帶頭節(jié)點的鏈表的插入， 首先使用臨時變量p等于要插入之前的節(jié)點（不管具體的插入位置） ，之后不管要插入的節(jié)點x是插到鏈表頭還是插到鏈表的其他位置都是如下語句: x->next = p->next;p->next = x;2.不帶頭結點的鏈表的插入， 若要插到鏈表的開頭則x->next = head->next;head = x;/這里不再是head->next = x若插到鏈表的其他位置則p = 插入之前的節(jié)點x->next = p->next;p->next = x;3.帶頭結點的鏈表的刪除， 不解釋，同

6、樣不存在刪除位置的差異。4.不帶頭結點的鏈表的刪除，刪除第一個節(jié)點時，head=head->next。刪除其他節(jié)點時，head的值不會改變。綜上所述，帶頭節(jié)點的單鏈表，不論刪除和插入的位置如何，不需要修改head的值，不帶頭結點的單鏈表則需要修改head的值。所以單鏈表 一般為帶頭結點的單鏈表 。論述如果矩陣A中存在這樣的一個元素Aij滿足條件：Aij是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。編寫一個函數(shù)計算出m×n的矩陣A的所有馬鞍點。提示：依題意，先求出每行的最小值元素，放入minm之中，再求出每列的最大值元素，放入maxn之中，若某元

7、素既在mini中，又在maxj中，則該元素Aij便是馬鞍點，找出所有這樣的元素,即找到了所有馬鞍點/#include "stdafx.h"/vc+6.0#include "stdio.h"void main(void) int a55,i,j,jj,n,m,x,max,f; printf("Enter m & n(Positive integer).n"); scanf("%d%d",&m,&n); printf("Type some data.n"); for(i=0;i<m;i+) for(j=0;j<n;scanf("%d",&aij+); for(max=(1<<sizeof(int)*8-1),f=i=0;i<m;i+) for(x=max,j=0;j<n;j+) if(x>aij)x=aijj=j; for(j=0;j<