數據結構c語言試卷
❶ 求解一道數據結構的題目，用c語言解，考試用的，急，謝謝。
特別說明：
把c1.h,C2-1.H,Bo2-1.cpp,Func2-2.cpp,
Main2-1.cpp 它們分別單獨存為文件，然後把他們放在一拆野喚個文件夾中，最後雙擊Main2-1.cpp。
// c1.h (文件名)
#include<string.h> // 字元串函數頭文件
#include<ctype.h> // 字元函數頭文件
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<io.h> // eof()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#include<sys/timeb.h> // ftime()
#include<stdarg.h> // 提供宏va_start，va_arg和va_end，用於存取變長參數表
// 函數結果狀態代碼。
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
/脊豎/ #define INFEASIBLE -1 沒使用
// #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3，故去掉此行
typedef int Status; // Status是函數的類型，其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型旅凱，其值是TRUE或FALSE，
// c2-1.h 線性表的動態分配順序存儲結構。
#define LIST_INIT_SIZE 10 // 線性表存儲空間的初始分配量
#define LIST_INCREMENT 2 // 線性表存儲空間的分配增量
struct SqList
{ ElemType *elem; // 存儲空間基址
int length; // 當前長度
int listsize; // 當前分配的存儲容量(以sizeof(ElemType)為單位)
};
// bo2-1.cpp 順序存儲的線性表(存儲結構由c2-1.h定義)的基本操作(12個)，包括演算法2.3～2.6
void InitList(SqList &L) // 演算法2.3
{ // 操作結果：構造一個空的順序線性表L
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) // 存儲分配失敗
exit(OVERFLOW);
L.length=0; // 空表長度為0
L.listsize=LIST_INIT_SIZE; // 初始存儲容量
}
void DestroyList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L
free(L.elem); // 釋放L.elem所指的存儲空間
L.elem=NULL; // L.elem不再指向任何存儲單元
L.length=0;
L.listsize=0;
}
void ClearList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：將L重置為空表
L.length=0;
}
Status ListEmpty(SqList L)
{ // 初始條件：順序線性表L已存在。
// 操作結果：若L為空表，則返回TRUE；否則返回FALSE
if(L.length==0)
return TRUE;
else
return FALSE;
}
int ListLength(SqList L)
{ // 初始條件：順序線性表L已存在。操作結果：返回L中數據元素的個數
return L.length;
}
Status GetElem(SqList L,int i,ElemType &e)
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：用e返回L中第i個數據元素的值
if(i<1||i>L.length) // i不在表L的范圍之內
return ERROR;
e=*(L.elem+i-1); // 將表L的第i個元素的值賦給e
return OK;
}
int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始條件：順序線性表L已存在，compare()是數據元素判定函數(滿足為1，否則為0)
// 操作結果：返回L中第1個與e滿足關系compare()的數據元素的位序。
// 若這樣的數據元素不存在，則返回值為0。演算法2.6
int i=1; // i的初值為第1個元素的位序
ElemType *p=L.elem; // p的初值為第1個元素的存儲位置
while(i<=L.length&&!compare(*p++,e)) // i未超出表的范圍且未找到滿足關系的數據元素
++i; // 繼續向後找
if(i<=L.length) // 找到滿足關系的數據元素
return i; // 返回其位序
else // 未找到滿足關系的數據元素
return 0;
}
Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅；
// 否則操作失敗，pre_e無定義
int i=2; // 從第2個元素開始
ElemType *p=L.elem+1; // p指向第2個元素
while(i<=L.length&&*p!=cur_e) // i未超出表的范圍且未找到值為cur_e的元素
{ p++; // p指向下一個元素
i++; // 計數加1
}
if(i>L.length) // 到表結束處還未找到值為cur_e的元素
return ERROR; // 操作失敗
else // 找到值為cur_e的元素，並由p指向其
{ pre_e=*--p; // p指向前一個元素(cur_e的前驅)，將所指元素的值賦給pre_e
return OK; // 操作成功
}
}
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
int i=1; // 從第1個元素開始
ElemType *p=L.elem; // p指向第1個元素
while(i<L.length&&*p!=cur_e) // i未到表尾且未找到值為cur_e的元素
{ p++; // p指向下一個元素
i++; // 計數加1
}
if(i==L.length) // 到表尾的前一個元素還未找到值為cur_e的元素
return ERROR; // 操作失敗
else // 找到值為cur_e的元素，並由p指向其
{ next_e=*++p; // p指向下一個元素(cur_e的後繼)，將所指元素的值賦給next _e
return OK; // 操作成功
}
}
Status ListInsert(SqList &L,int i,ElemType e) // 演算法2.4
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)+1
// 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1
ElemType *newbase,*q,*p;
if(i<1||i>L.length+1) // i值不合法
return ERROR;
if(L.length==L.listsize) // 當前存儲空間已滿，增加分配，修改
{ newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));
if(!newbase) // 存儲分配失敗
exit(OVERFLOW);
L.elem=newbase; // 新基址賦給L.elem
L.listsize+=LIST_INCREMENT; // 增加存儲容量
}
q=L.elem+i-1; // q為插入位置
for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之後的元素右移(由表尾元素開始移)
*(p+1)=*p;
*q=e; // 插入e
++L.length; // 表長增1
return OK;
}
Status ListDelete(SqList &L,int i,ElemType &e) // 演算法2.5
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p為被刪除元素的位置
e=*p; // 被刪除元素的值賦給e
q=L.elem+L.length-1; // q為表尾元素的位置
for(++p;p<=q;++p) // 被刪除元素之後的元素左移(由被刪除元素的後繼元素開始移)
*(p-1)=*p;
L.length--; // 表長減1
return OK;
}
void ListTraverse(SqList L,void(*visit)(ElemType&))
{ // 初始條件：順序線性表L已存在
// 操作結果：依次對L的每個數據元素調用函數visit()
// visit()的形參加'&'，表明可通過調用visit()改變元素的值
ElemType *p=L.elem; // p指向第1個元素
int i;
for(i=1;i<=L.length;i++) // 從表L的第1個元素到最後1個元素
visit(*p++); // 對每個數據元素調用visit()
printf("\n");
}
// func2-2.cpp 幾個常用的函數
Status equal(ElemType c1,ElemType c2)
{ // 判斷是否相等的函數
if(c1==c2)
return TRUE;
else
return FALSE;
}
int comp(ElemType a,ElemType b)
{ // 根據a<、=或>b，分別返回-1、0或1
if(a==b)
return 0;
else
return (a-b)/abs(a-b);
}
void print(ElemType c)
{ // 以十進制整型的格式輸出元素的值
printf("%d ",c);
}
void print1(ElemType &c)
{ // 以十進制整型的格式輸出元素的值(設c為引用類型)
printf("%d ",c);
}
void print2(ElemType c)
{ // 以字元型的格式輸出元素的值
printf("%c ",c);
}
// main2-1.cpp 檢驗bo2-1.cpp的主程序
#include"c1.h"
typedef int ElemType; // 定義ElemType為整型
#include"c2-1.h" // 線性表的順序存儲結構
#include"bo2-1.cpp" // 線性表順序存儲結構的基本操作
#include"func2-2.cpp" // 包括equal()、comp()、print()、print1()和print2()函數
Status sq(ElemType c1,ElemType c2)
{ // 數據元素判定函數(平方關系)，LocateElem()調用的函數
if(c1==c2*c2)
return TRUE;
else
return FALSE;
}
void dbl(ElemType &c)
{ // ListTraverse()調用的另一函數(元素值加倍)
c*=2;
}
void main()
{
SqList L;
ElemType e,e0;
Status i;
int j,k;
InitList(L); // 初始化線性表L
printf("初始化L後，L.length=%d，L.listsize=%d，L.elem=%u\n",L.length,
L.listsize,L.elem);
for(j=1;j<=5;j++)
i=ListInsert(L,1,j); // 在L的表頭插入j
printf("在L的表頭依次插入1～5後，*L.elem=");
for(j=1;j<=5;j++)
printf("%d ",*(L.elem+j-1)); // 依次輸出表L中的元素
printf("\n調用ListTraverse()函數，依次輸出表L中的元素：");
ListTraverse(L,print1); // 依次對表L中的元素調用print1()函數(輸出元素的值)
i=ListEmpty(L); // 檢測表L是否空
printf("L.length=%d(改變)，L.listsize=%d(不變)，",L.length,L.listsize);
printf("L.elem=%u(不變)，L是否空？i=%d(1:是 0:否)\n",L.elem,i);
ClearList(L); // 清空表L
i=ListEmpty(L); // 再次檢測表L是否空
printf("清空L後，L.length=%d，L.listsize=%d，",L.length,L.listsize);
printf("L.elem=%u，L是否空？i=%d(1:是 0:否)\n",L.elem,i);
for(j=1;j<=10;j++)
ListInsert(L,j,j); // 在L的表尾插入j
printf("在L的表尾依次插入1～10後，L=");
ListTraverse(L,print1); // 依次輸出表L中的元素
printf("L.length=%d，L.listsize=%d，L.elem=%u\n",L.length,L.listsize,L.elem);
ListInsert(L,1,0); // 在L的表頭插入0，增加存儲空間
printf("在L的表頭插入0後，L.length=%d(改變)，L.listsize=%d(改變)，"
"L.elem=%u(有可能改變)\n",L.length,L.listsize,L.elem);
GetElem(L,5,e); // 將表L中的第5個元素的值賦給e
printf("第5個元素的值為%d\n",e);
for(j=10;j<=11;j++)
{ k=LocateElem(L,j,equal); // 查找表L中與j相等的元素，並將其位序賦給k
if(k) // k不為0，表明有符合條件的元素
printf("第%d個元素的值為%d，",k,j);
else // k為0，沒有符合條件的元素
printf("沒有值為%d的元素\n",j);
}
for(j=3;j<=4;j++) // 測試2個數據
{ k=LocateElem(L,j,sq); // 查找表L中與j的平方相等的元素，並將其位序賦給k
if(k) // k不為0，表明有符合條件的元素
printf("第%d個元素的值為%d的平方，",k,j);
else // k為0，沒有符合條件的元素
printf("沒有值為%d的平方的元素\n",j);
}
for(j=1;j<=2;j++) // 測試頭2個數據
{ GetElem(L,j,e0); // 將表L中的第j個元素的值賦給e0
i=PriorElem(L,e0,e); // 求e0的前驅，如成功，將值賦給e
if(i==ERROR) // 操作失敗
printf("元素%d無前驅，",e0);
else // 操作成功
printf("元素%d的前驅為%d\n",e0,e);
}
for(j=ListLength(L)-1;j<=ListLength(L);j++) // 最後2個數據
{ GetElem(L,j,e0); // 將表L中的第j個元素的值賦給e0
i=NextElem(L,e0,e); // 求e0的後繼，如成功，將值賦給e
if(i==ERROR) // 操作失敗
printf("元素%d無後繼\n",e0);
else // 操作成功
printf("元素%d的後繼為%d，",e0,e);
}
k=ListLength(L); // k為表長
for(j=k+1;j>=k;j--)
{ i=ListDelete(L,j,e); // 刪除第j個數據
if(i==ERROR) // 表中不存在第j個數據
printf("刪除第%d個元素失敗。",j);
else // 表中存在第j個數據，刪除成功，其值賦給e
printf("刪除第%d個元素成功，其值為%d",j,e);
}
ListTraverse(L,dbl); // 依次對元素調用dbl()，元素值乘2
printf("L的元素值加倍後，L=");
ListTraverse(L,print1); // 依次輸出表L中的元素
DestroyList(L); // 銷毀表L
printf("銷毀L後，L.length=%d，L.listsize=%d，L.elem=%u\n",L.length,
L.listsize,L.elem);
}
❷ 數據結構（c語言版）題目求答案
3.28
void InitCiQueue(CiQueue&Q)//初始化循環鏈表表示的隊列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
voidEnCiQueue(CiQueue&Q,int x)//把元素x插入循環列表表示的隊列Q,Q指向隊尾元素，Q->next指向頭結點，Q->next->next指向隊尾元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;//直接把p加在Q的後面
Q->next=p;
Q=p;//修改尾指針
}
Status DeCiQueue(CiQueue&Q,int x)//從循環鏈表表示的隊列Q頭部刪除元素x
{
if(Q==Q->next)return INFEASIBLE;//隊列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
rturn OK;
}//DeCiqueue
3.31
int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}
❸ 急需數據結構C語言版（清華大學出版社）的期末考試試題及答案
《數據結構》期末考試試卷（ A ）
一、 選擇題（每小題2分，共24分）
1．計算機識別、存儲和加工處理的對象被統稱為( A )
A.數據 B.數據元素
C.數據結構 D.數據類型
2．棧和隊列都是（ A ）
A．限制存取位置的線性結構 B．順序存儲的線性結構
C．鏈式存儲的線性結構 D．限制存取位置的非線性結構
3．鏈棧與順序棧相比，比較明顯的優點是( D )
A.插入操作更加方便 B.刪除操作更加方便
C.不會出現下溢的情況 D.不會出現上溢的情況
4．採用兩類不同存儲結構的字元串可分別簡稱為( B )
A.主串和子串 B.順序串和鏈串
C.目標串和模式串 D.變數串和常量串
5． 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一種特殊的線性表，其特殊性體現在：B
A.可以順序存儲 B .數據元素是一個字元
C. 可以鏈接存儲 D. 數據元素可以是多個字元
7．設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為： C
A. 2h B .2h-1
C. 2h+1 D. h+1
軟體開發網
8．樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這里，我們把 由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。下列結論哪個正確？ A
A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
B .樹的後根遍歷序列與其對應的二叉樹的後序遍歷序列相同
C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
D. 以上都不對
9．一個有n個頂點的無向圖最多有多少邊？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一個圖中，所有頂點的度數之和等於所有邊數的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．當在二叉排序樹中插入一個新結點時，若樹中不存在與待插入結點的關鍵字相同的結點，且新結點的關鍵字小於根結點的關鍵字，則新結點將成為（ A ）
A．左子樹的葉子結點 B．左子樹的分支結點
C．右子樹的葉子結點 D．右子樹的分支結點
軟體開發網
12．對於哈希函數H(key)=key%13,被稱為同義詞的關鍵字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉樹的前序遍歷結果為A,B,D,E,G,C,F,H,I,J，其中中序遍歷的結果為D,B,G,E,A,H,F,I,J,C。請畫出二叉的具體結構。（注意要寫出具體步驟）（10分）
原理見課本128頁
三、有圖如下，請寫出從頂點c0出發的深度優先及寬度優先遍歷的結果。(10分)
深度優先；C0-C1-C3-C4-C5-C2
寬度優先：C0-C1-C2-C3-C4-C5
四、有圖如下，按Kruskal演算法求出其最小生成樹。要求寫出完整的步驟。（10分）
原理見課本250頁
五、給定線性表（12，23，45，66，76，88，93，103，166），試寫出在其上進行二分查找關鍵字值12，93，166的過程。並寫出二分查找的演算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
過程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
演算法：見課本84頁上
六、知單鏈表的結點結構為
Data next
下列演算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。
請在空缺處填入合適的內容，使其成為完整的演算法。 (可用文字說明該演算法的基本思想及執行的過程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本題不會。嘿嘿。。。。
七、一個完整的演算法應該具有哪幾個基本性質？分別簡要說明每一性質的含意。(5分)
輸入：
四個基本性質：1.輸入：有零個或多個有外部提供的量作為演算法的輸入
2：輸出：演算法產生至少一個量作為輸出
3.：確定性：組成演算法的每條指令是清晰的，無歧異的。
4.：有限性：演算法中每條指令的執行次數是有限的，執行每條指令的時間也是有限的
八、何謂隊列的"假溢"現象？如何解決？（5分）
隊列的假溢現象是指數組實現的順序隊列中，隊尾指針已到達數組的下表上界產生上溢而隊頭指針之前還有若干 空間閑置的現象。解決的辦法之一是利用循環隊列技術使數組空間的首尾相連。
九、說明並比較文件的各種物理結構。（6分）
❹ c語言題型，數據結構題
#include <stdio.h>
#include <malloc.h>
typedef struct student
{
char name[20];
long num;
char sex;
struct student *pNext;
}Stu, *pStu;
void creatInfo(pStu *stu);
int deletInfo(pStu stu, long numTemp);
void printInfo(pStu stu);
int main(void)
{
long numTemp = 0;
pStu myStu = NULL;
creatInfo(&myStu);
scanf("%ld", &搏御numTemp);
if(1 == deletInfo(myStu, numTemp))
printInfo(myStu);
return 0;
}
void creatInfo(pStu *stu)
{
int n = 1;
pStu pNew = NULL, pTail = NULL;
*stu = (pStu)malloc(sizeof(Stu));
if(*stu == NULL)
return ;
(*stu)->pNext = NULL;
pTail = *stu;
while(n <= 10)
{
pNew = (pStu)malloc(sizeof(Stu));
if(NULL == pNew)
return ;
pNew->pNext = NULL;
scanf("%s", pNew->name);
if('#' == pNew->name[0])
{
free(pNew);
pNew = NULL;
return ;
}
scanf("%ld %c", &pNew->num, &pNew->sex);
pTail->薯行pNext = pNew;
pTail = pNew;
++n;
}
}
int deletInfo(pStu stu, long numTemp)
{
pStu pTail = NULL, pHead = NULL;
pHead = stu;
pTail = stu->pNext;
while(pTail)
{
if(pTail->num == numTemp)
{
pHead->pNext = pTail->pNext;
free(pTail);
pTail = NULL;
return 1;
}
pTail = pTail->pNext;
pHead = pHead->pNext;
}
printf("鏈表中唔基手岩該學生！ ");
return 0;
}
void printInfo(pStu stu)
{
while(stu = stu->pNext)
printf("%s, %d, %c ", stu->name, stu->num, stu->sex);
}