- 相關推薦
2016年計算機筆試考試題及答案
2016年計算機等級考試就要開始了,同學們復習好了嗎?下面yjbys小編為大家準備的是關于網絡筆試的考試題及答案,希望能幫助大家順利通過考試!
【字符串】
1、輸入一個字符串,打印出該字符串中字符的所有排列。
例如輸入字符串abc,則輸出由字符a、b、c所能排列出來的所有字符串abc、acb、bac、bca、cab和cba。
2、有一個由大小寫組成的字符串,現在需要對他進行修改,將其中的所有小寫字母排在大寫字母的前面
(大寫或小寫字母之間不要求保持原來次序),如有可能盡量選擇時間和空間效率高的算法。
c語言函數原型void proc(char *str),也可以采用你自己熟悉的語言。
3、編寫反轉字符串的程序,要求優化速度、優化空間。
4、用C語言實現函數void * memmove(void *dest, const void *src, size_t n)。
memmove函數的功能是拷貝src所指的內存內容前n個字節到dest所指的地址上。
分析:由于可以把任何類型的指針賦給void類型的指針,這個函數主要是實現各種數據類型的拷貝。
5、編程找出兩個字符串中最大公共子字符串,如"abccade", "dgcadde"的最大子串為"cad"。
6、輸入一個字符串,輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串"google",由于該字符串里最長的對稱子字符串是"goog",因此輸出4。
7、字符串原地壓縮。題目描述:“eeeeeaaaff" 壓縮為 "e5a3f2",請編程實現。
8、請以回溯與不回溯算法實現字符串匹配。
9、輸入一個英文句子,翻轉句子中單詞的順序,但單詞內字符的順序不變。句子中單詞以空格符隔開。
為簡單起見,標點符號和普通字母一樣處理。
例如:輸入"I am a student.",則輸出"student. a am I"。
10、在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff,則輸出b。
11、寫一個函數,它的原形是int continumax(char *outputstr,char *intputstr)
功能:
在字符串中找出連續最長的數字串,并把這個串的長度返回,并把這個最長數字串付給其中一個函數參數outputstr所指內存。
例如:"abcd12345ed125ss123456789"的首地址傳給intputstr后,函數將返回9,outputstr所指的值為123456789。
12、定義字符串的左旋轉操作:把字符串前面的若干個字符移動到字符串的尾部。
如:把字符串abcdef左旋轉2位得到字符串cdefab。請實現字符串左旋轉的函數。
要求時間對長度為n的字符串操作的復雜度為O(n),輔助內存為O(1)。
13、有n個長為m+1的字符串,如果某個字符串的最后m個字符與某個字符串的前m個字符匹配,則兩個字符串可以聯接。
問這n個字符串最多可以連成一個多長的字符串,如果出現循環,則返回錯誤。
14、如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中,則字符串一稱之為字符串二的子串。
注意,并不要求子串(字符串一)的字符必須連續出現在字符串二中。
請編寫一個函數,輸入兩個字符串,求它們的最長公共子串,并打印出最長公共子串。
例如:輸入兩個字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它們的最長公共子串,
則輸出它們的長度4,并打印任意一個子串。
分析:求最長公共子串(Longest Common Subsequence, LCS)是一道非常經典的動態規劃題。
15、輸入兩個字符串,從第一字符串中刪除第二個字符串中所有的字符。
例如,輸入"They are students."和"aeiou",則刪除之后的第一個字符串變成"Thy r stdnts."。
16、一個文件,內含一千萬行字符串,每個字符串在1K以內,要求找出所有相反的串對,如abc和cba。
17、給出一個函數來復制兩個字符串A和B。字符串A的后幾個字節和字符串B的前幾個字節重疊。
18、已知一個字符串,比如asderwsde,尋找其中的一個子字符串比如sde的個數,如果沒有返回0,有的話返回子字符串的個數。
19、求最大連續遞增數字串(如"ads3sl456789DF3456ld345AA"中的"456789")。
20、實現strstr功能,即在父串中尋找子串首次出現的位置。
21、編碼完成下面的處理函數。
函數將字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改變非'*'字符的先后順序,函數返回串中字符'*'的數量。
如原始串為:ab**cd**e*12,處理后為*****abcde12,函數并返回值為5。(要求使用盡量少的時間和輔助空間)
22、刪除字符串中的數字并壓縮字符串。如字符串”abc123de4fg56”處理后變為”abcdefg”。注意空間和效率。
23、求兩個串中的第一個最長子串(神州數碼以前試題)。如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。
【棧、鏈表、樹、圖】
1、編寫一個程序,把一個有序整數數組放到二叉樹中。
2、編程實現從頂部開始逐層打印二叉樹節點數據。[參考]
3、編程實現單鏈表逆轉。
4、設計一個算法,找出二叉樹上任意兩個結點的最近共同父結點。復雜度不能為O(n2)。
5、二叉排序樹中,令f = (最大值+最小值) / 2,設計一個算法,找出距離f值最近、大于f值的結點。復雜度不能為O(n2)。
6、有雙向循環鏈表結點定義為:
struct node
{
int data;
struct node *front,*next;
};
有兩個雙向循環鏈表A,B,知道其頭指針為:pHeadA、pHeadB,請寫一函數將兩鏈表中data值相同的結點刪除。
更多相關文章推薦閱讀:
7、輸入一個鏈表的頭結點,從尾到頭反過來輸出每個結點的值。鏈表結點定義如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
8、輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的結點,只調整指針的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹 節點的數據結構如下:
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
}; [參考]
9、設計包含min函數的棧。
定義棧的數據結構,要求添加一個min函數,能夠得到棧的最小元素。
要求函數min、push以及pop的時間復雜度都是O(1)。
10、輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
打印出和與輸入整數相等的所有路徑。
例如 輸入整數22和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑:10, 12和10, 5, 7。
二元樹節點的數據結構定義為:
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
11、給出倆個單向鏈表的頭指針,比如h1,h2,判斷這倆個鏈表是否相交。為了簡化問題,我們假設倆個鏈表均不帶環。
問題擴展:
(1) 如果鏈表可能有環列?
(2) 如果需要求出倆個鏈表相交的第一個節點列?
12、輸入一個整數數組,判斷該數組是不是某二元查找樹的后序遍歷的結果。
如果是返回true,否則返回false。
例如輸入5、7、6、9、11、10、8,由于這一整數序列是如下樹的后序遍歷結果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結果是這個序列,因此返回false。
13、如果我們把二叉樹看成一個圖,父子節點之間的連線看成是雙向的,我們姑且定義"距離"為兩節點之間邊的個數。
寫一個程序,求一棵二叉樹中相距最遠的兩個節點之間的距離。
14、輸入一個單向鏈表,輸出該鏈表中倒數第k個結點。鏈表的倒數第0個結點為鏈表的尾指針。
鏈表結點定義如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
15、輸入一顆二元查找樹,將該樹轉換為它的鏡像,即在轉換后的二元查找樹中,左子樹的結點都大于右子樹的結點。
用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入:
8
/ \
6 10
/\ /\
5 7 9 11
輸出:
8
/ \
10 6
/ \/ \
11 97 5
定義二元查找樹的結點為:
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
}; [參考]
16、求一個二叉樹中任意兩個節點間的最大距離,兩個節點的距離的定義是 這兩個節點間邊的個數。
比如某個孩子節點和父節點間的距離是1,和相鄰兄弟節點間的距離是2,優化時間空間復雜度。
17、求一個有向連通圖的割點,割點的定義是,如果除去此節點和與其相關的邊,有向圖不再連通,描述算法。
18、設計一個棧結構,滿足一下條件:min,push,pop操作的時間復雜度為O(1)。
19、請修改append函數,利用這個函數實現:
兩個非降序鏈表的并集,1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結果,不能修改兩個鏈表的數據。
20、遞歸和非遞歸倆種方法實現二叉樹的前序遍歷。
21、輸入一棵二元樹的根結點,求該樹的深度。
從根結點到葉結點依次經過的結點(含根、葉結點)形成樹的一條路徑,最長路徑的長度為樹的深度。
22、用倆個棧實現隊列,某隊列的聲明如下:
template class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T m_stack1;
T m_stack2;
};
23、給定鏈表的頭指針和一個結點指針,在O(1)時間刪除該結點。鏈表結點的定義如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數的聲明如下:void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
24、兩個單向鏈表,找出它們的第一個公共結點。
更多相關文章推薦閱讀:
鏈表的結點定義為:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
25、用遞歸顛倒一個棧。例如輸入棧{1, 2, 3, 4, 5},1在棧頂。顛倒之后的棧為{5, 4, 3, 2, 1},5處在棧頂。
26、二叉樹的結點定義如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入二叉樹中的兩個結點,輸出這兩個結點在數中最低的共同父結點。
27、有一個復雜鏈表,其結點除了有一個m_pNext指針指向下一個結點外,還有一個m_pSibling指向鏈表中的任一結點或者NULL。
其結點的C++定義如下:
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下圖是一個含有5個結點的該類型復雜鏈表。
圖中實線箭頭表示m_pNext指針,虛線箭頭表示m_pSibling指針。為簡單起見,指向NULL的指針沒有畫出。
請完成函數ComplexNode* Clone(ComplexNode* pHead),以復制一個復雜鏈表。
28、給定單鏈表、檢測是否有環。
29、給定兩個單鏈表(head1, head2),檢測兩個鏈表是否有交點,如果有返回第一個交點。
30、給定單鏈表(head),如果有環的話請返回從頭結點進入環的第一個節點。
31、只給定單鏈表中某個結點p(并非最后一個結點,即p->next!=NULL)指針,刪除該結點。
32、只給定單鏈表中某個結點p(非空結點),在p前面插入一個結點。
33、編寫實現鏈表排序的一種算法。說明為什么你會選擇用這樣的方法?
34、編寫實現數組排序的一種算法。說明為什么你會選擇用這樣的方法?
35、怎樣編寫一個程序,把一個有序整數數組放到二叉樹中?
更多相關文章推薦閱讀:
【計算機筆試考試題及答案】相關文章:
大學計算機基礎考試題及答案08-05
2017計算機考試題目及答案06-15
計算機考試題庫及答案06-06
大學基礎計算機考試題及答案08-05
計算機一級考試題庫筆試大題06-21
2017計算機期末考試題及答案06-21
計算機基礎考試題庫附答案11-01
計算機基礎知識考試題附答案04-30